The simplest nonlinear operator is a scalar function $f\left(x\right)$, and a basic problem is to find the null set of $f$, those values $x$ for which $f\left(x\right)=0$, known as the roots of $f$.

Consider $f\left(x\right)=p_8\left(x\right)={\sum }_{i=0}^8{a}_i{x}^i$, an eigth degree polynomial with $𝒂=\left[\begin{array}{lll}{a}_0& \dots & a_8\end{array}\right]$

1Track 1

Implement each of the following methods to find a root of $p_8$.

1. Seek a root $r\in [5.5,6.5]$ using the bisection algorithm (see course webpage).

2. Seek $r$ by the secant method.

3. Seek $r$ by Newton's method.

4. Seek $r$ by Steffensen's method.

5. Change $a_7=-36-{10}^{-3}$ and repeat the above

2Track 2

1. Prove that Steffensen's method is of second order.

2. Implement Steffensen's and find $r\in [5.5,6.5]$, a root of a perturbed ${\stackrel{\sim }{p}}_8\left(t\right)$, where ${\stackrel{\sim }{a}}_2=a_2+{\epsilon }_k$, ${\epsilon }_k=2^{-k}$, $k\in \{15,14,\dots ,10\}$. Comment on what you observe.

3. Apply the vector-valued version of Newton's method

   ${\displaystyle {𝒙}_{n+1}={𝒙}_n-{𝑱}_n^{-1}𝒇\left({𝒙}_n\right),}$

   (1)

   where ${𝑱}_n$ is the Jacobian

   ${\displaystyle {𝑱}_n={𝒇}^{\text{'}}\left({𝒙}_n\right)=\frac{\partial 𝒇}{\partial 𝒙}\left({𝒙}_n\right),}$

   to find a root of

   ${\displaystyle \{\begin{array}{l}uv-w^2=1\\ uvw-u^2+v^2=2\\ e^u-e^v+w=3\end{array}..}$

   Implementation notes:

   • As usual, ${𝑱}^{-1}$ is implemented as linear system solve

     ${\displaystyle 𝑱𝒔=𝒇\left({𝒙}_n\right)\Rightarrow {𝒙}_{n+1}={𝒙}_n+𝒔}$

   • An initial guess is typically obtained by linearization of the system.