Write a program to implement the fixed point iteration scheme

xn$+1=$ g$($xn$)$

for general g$.$ Provide for termination of the process as soon as $|$xn $$ xn$1|<$ or when n $=$ Nmax,

whichever occurs first. Your fixed point function should return the iterates xn and should print out on

the screen the values of n and xn for each n$,$ so that you can watch the progress of the iteration.

$($a$)$ Show by hand calculation that using g$($x$)=$ x $$ h$($F $($x$)),$ with h$($F $)=$ F

$2+$ k for some constant

k you are solving equation $(1).$

$($b$)$ Run your program with k $=0,=105,$ x$0=3,$ and Nmax $=10.$

i$.$ Plot Analysis: Plot y $=$ g$($x$)$ and y $=$ x on the same graph. Identify the fixed point as the

intersection of y $=$ g$($x$)$ and y $=$ x$.$ On this plot:

$$ Mark each iterate $($xn$,$ g$($xn$))$ up to the first three iterates to visualize the sequence$$s

progression in relation to the fixed point.

$$ Draw dashed vertical lines from each point $($xn$,$ xn$)$ to $($xn$,$ g$($xn$)).$

$$ Draw dashed horizontal lines from each point $($xn$,$ g$($xn$))$ to $($g$($xn$),$ g$($xn$)).$

ii$.$ Convergence Assessment:

$$ Observe the behavior of the iterates over these first three steps. Do they appear to

approach or move away from the fixed point?

$$ Based on your observations and understanding of fixed$-$point iteration, explain why con$-$

vergence might or might not occur in this case.

$($c$)$ Determine the values of k for which convergence is guaranteed if xn remains in the range $($$,$$/2).$

$($d$)$ Choose, giving reasons, a value of k for which monotonic convergence should occur near the

root, and also a value for which oscillatory convergence should occur near the root. $($Look my

supplemental notes $$rootfinding part$2$ page $21).$ Verify that these two values of k give the

expected behavior, by running the program with Nmax $=20,=105$ and x$0=2($please

choose values that help to illustrate the behavior clearly! Mark the iterates and draw vertical

and horizontal dashed lines like in $2($b$).$ Adjust your viewing window so the behavior is shown

clearly$).$

$($e$)$ Also run the case k $=16$ and $=105$ and x$0=2.$ This should converge slowly, so set

Nmax $=50.$ Discuss whether the termination criterion $|$xn $$ xn$1|<,$ ensures that the absolute

error, $|$xn $$ $|,$ is less than $105$ in this case? $($Use formula $(7\mathrm{.}30)$ in $$rootfinding part$2$ page

$36$ that gives a good approximation of the actual error, read also the corresponding slides to

understand the idea around it and how the iteration can be speed up using Aitken$$s extrapolation$)$

$($f$)$ Discuss whether your previous convergence results $($for $(2))$ are consistent with first$-$order conver$-$

gence.