Question $2$

$($a$)$ Write a function that implements the following pseudo$-$code:

Input: $f,f^{\text{'}},x,lon,N.$

Output: $x^{**}.$

Repeat $N$ times:

$($a$)$ Set $y_1=x.$

$($b$)$ Take one Newton step, starting from $y_1.$ Call the result $y_2.$

$($c$)$ Take one Newton step, starting from $y_2.$ Call the result $y_3.$

$($d$)$ Set

$x=y_1-\frac{(y_2-y_1{)}^2}{y_3-2y_2+y_1}$

$($e$)$ Display $|f(x)|.$

$($f$)$ If $|f(x)|<mi\; id="EditorElement\_431902"></mi><mi\; id="EditorElement\_431904">l</mi><mi\; id="EditorElement\_431906">o</mi><mi\; id="EditorElement\_431908">n</mi>$ print "converged!", break.

Output $x^{**}=x.$

This algorithm is called Steffensen's iteration.

$($b$)$ Test your routine on the problem

exp$(-x^2+x)-\frac{1}{2}x=1\mathrm{.}0836(with$ initial guess $x=1)$

Show that Newton iteration does not converge quadratically, but your new iterative algorithm

does.

steff.$py$

import numpy as np

def steff$($f$,$fp$,$x$,$epse,epsr,itmx$)$:

# Steffensen iteration for f$($x$)=0.$

# Input: function handles f and f$\text{'},$ floats inital guess x$,$ tolerance for error $($epse$)$ and residual $($epsr$),$ integer max nur of iterations itmx.

# Output: approximate solution x$,$ estimate of error, residual.

$...$ initializations $...$

for i in range$(...)$: # Loop over iterations.

if $...$ : # Check for convergence.

$...$

if $...$ # Print warning message if there was no convergence.

print$(...)$

return x$,$err,res # Return floats: approximate root x$,$ approximate error err and residual res.

$stef{f}_s$cript.$py$

import numpy as np

from steff import steff

from newton import newton

# Question $2$

def f$($x$)$:

return

def fp$($x$)$:

return

# Find reasonable values for residual and error tolerance and the number of iterations:

tol$\_$err $=$

tol$\_$res $=$

itmax $=$

# initial point

x$0=1\mathrm{.}0$

# First try Newton iteration:

print$("$Calling Newton function..."$)$

x$,$err,res $=$ newton$(...)$

# That converges slowly, now try steffenson

print$("$Calling Steffensen function..."$)$

x$,$err,res $=$ steff$(...)$