Skip to main content

Numerical Methods · Root finding and nonlinear systems

A fixed-point rearrangement is useless unless it contracts on an invariant interval

Problem

Numerical Methods practice problem

Let I=[1/2,1]I=[1/2,1] and let f(x)=x2+x−1f(x)=x^2+x-1. A root of ff in II is a fixed point of any gg satisfying g(x)=x  ⟺  f(x)=0g(x)=x\iff f(x)=0 at that point. Consider the three candidate rearrangementsgA(x)=1−x2,gB(x)=11+x,gC(x)=1−x,\begin{align*} g_A(x)&=1-x^2,\\ g_B(x)&=\frac1{1+x},\\ g_C(x)&=\sqrt{1-x}, \end{align*}each of which is algebraically equivalent to f(x)=0f(x)=0 wherever it is defined and the original equation holds.

1. State the contraction-mapping theorem on a closed real interval: if g:I→Ig:I\to I satisfies ∣g(x)−g(y)∣≤k∣x−y∣|g(x)-g(y)|\le k|x-y| for some k∈[0,1)k\in[0,1) and all x,y∈Ix,y\in I, then gg has a unique fixed point L∈IL\in I, the Picard iterates xn+1=g(xn)x_{n+1}=g(x_n) converge to LL from every x0∈Ix_0\in I, and∣xn−L∣≤kn1−k∣x1−x0∣.|x_n-L|\le\frac{k^n}{1-k}|x_1-x_0|.Prove uniqueness and the displayed a priori bound from the geometric estimate ∣xj+1−xj∣≤k∣xj−xj−1∣|x_{j+1}-x_j|\le k|x_j-x_{j-1}|. If gg is differentiable, record the mean-value test ∣g′∣≤k|g'|\le k on II.

2. For each of gAg_A, gBg_B, and gCg_C, decide whether g(I)⊆Ig(I)\subseteq I and whether sup⁡I∣g′∣<1\sup_I|g'|<1 (where the derivative exists). Select the unique candidate that is a contraction self-map of II, and exhibit an explicit Lipschitz constant k<1k<1.

3. Starting from x0=1x_0=1, compute the Picard iterates x1,…,x4x_1,\ldots,x_4 of the successful map as exact rationals. Identify the sequence with consecutive Fibonacci ratios and evaluate the exact limit LL.

4. Apply the a priori bound of part 1 at n=4n=4 with your kk. Compare it with the true error ∣x4−L∣|x_4-L|. Explain why an algebraically correct rearrangement can still be an illegal iteration on II, using gAg_A as the witness. Do not replace the argument by a Newton basin analysis.

Do not declare a map usable on II merely because it shares the correct fixed-point equation.

Hint

Hint

Uniqueness is immediate from (1−k)∣x−y∣≤0(1-k)|x-y|\le 0. The a priori bound is the tail of a geometric series of increments.

Check your work

Work the problem yourself first. Then open it in Training to check your answer and read the full worked solution.

The answer check and full solution for this problem come with ProofAnvil Practice membership ($19 USD monthly). See membership. Or start with the free Numerical Methods sample problem: Try the free sample problem.

More Numerical Methods practice problems

Back to Numerical Methods

An original ProofAnvil practice problem, written for this course. ProofAnvil is a practice course, not a homework-answer service.