程序代写代做代考 C algorithm Numerical Methods & Scientific Computing: lecture notes

Numerical Methods & Scientific Computing: lecture notes
Root-finding
Newton’s method
slope = f’(xn)
y
xn+1
y = f(x)
based on slope of function
xn
x

Numerical Methods & Scientific Computing: lecture notes
Root-finding
Derivation
Taylor series around xn:
f(xn+1)⇡f(xn)+f0(xn)(xn+1 xn)=0
which gives
Newton-Raphson iteration:
xn+1 = xn f (xn) . f0(xn)
Again, a first order recurrence relation. =) we expect problems if f 0(xn) = 0

Numerical Methods & Scientific Computing: lecture notes
Root-finding
Simple roots
Definition
f hasasimplerootatx⇤ iff(x⇤)=0,f0(x⇤)6=0.
Definition
f hasadoublerootatx⇤ iff(x⇤)=0,f0(x⇤)=0,f00(x⇤)6=0.
=) Newton’s method has trouble at a double root Example

Numerical Methods & Scientific Computing: lecture notes
Root-finding
Convergence rates
At a simple root:
e n + 1 ⇠ C e n2 quadratic convergence
At a double root:
linear convergence
en+1 ⇠ Cen
Definition
Order of convergence If en+1 ⇠ Cenp =) order of convergence = p

Numerical Methods & Scientific Computing: lecture notes
Root-finding
Explanation by Taylor series …
Can derive this more rigorously.

Numerical Methods & Scientific Computing: lecture notes
Root-finding
Linear convergence
Write en = 10bn
bn = number of correct decimal digits Linear Convergence =)
en+1⇡Cen, C<1 =) bn+1 ⇡ bn log10 C ! number of correct digits increases by a constant Numerical Methods & Scientific Computing: lecture notes Root-finding Quadratic Convergence =) e n + 1 ⇡ C e n2 ) bn+1 ⇡ 2bn log10 C ! number of correct digits doubles each iteration!! =) Quadratic Convergence very desirable Numerical Methods & Scientific Computing: lecture notes Root-finding Problems with Newton’s method f 0(x) may be hard to calculate it may not converge 🙁 Theorem Iff00(x)isC1 then9>0suchthat 8×0 2[x⇤,x⇤+],Newton’s method converges to the root x⇤
=) converges provided we start close enough BUT
don’t know x⇤ don’t know
=) get close with a globally convergent method, then switch to a fast method
! hybrid method

Numerical Methods & Scientific Computing: lecture notes
Root-finding
Convex functions
Note: for some functions, Newton’s method is guaranteed to converge
Example

Numerical Methods & Scientific Computing: lecture notes
Root-finding
Secant method
What if the derivative is really nasty? =) try the secant method instead, which doesn’t need the derivative function.
The secant method.
For this method, use two current “guesses” at a root of f (x) = 0. Want to replace the pair x0,x1 by the pair x1,x2 where x2 is a new guess. Use the straight line L from (x0, f (x0)) to (x1, f (x1)) ( a secant of the curve y = f (x)) to give the slope.

Numerical Methods & Scientific Computing: lecture notes
Root-finding
y
xn+1
slope = ∆y/∆x
y = f(x)
xn
x
xn-1

Numerical Methods & Scientific Computing: lecture notes
Root-finding
Secant method algorithm
Just replace f 0(xn) from NR method by
f (xn) f (xn1)
xn xn1
which gives
Secant method:
xn+1 =xn f(xn) xn xn1 . f (xn) f (xn1)
Since each new guess depends on the previous two guesses =) a second order recurrence relation.

Numerical Methods & Scientific Computing: lecture notes
Root-finding
Properties
The secant method:
quite ecient: converges quickly towards a root 🙂 must start with two guesses 🙁
don’t need derivative 🙂

Numerical Methods & Scientific Computing: lecture notes
Root-finding
Order of convergence
Using Taylor series, ! (at simple root)
en+1 ⇠ Cenen1
=) en+1 ⇠ Cenp where p = 1+p5 ⇡ 1.618 2
=) secant is superlinearly convergent but not quadratically convergent
(but only need 1 function evaluation/iteration; Newton needs 2)

Numerical Methods & Scientific Computing: lecture notes
Root-finding
Summary
fixed point bisection Newton Newton secant
en+1 ⇠ Cen en+1 ⇠ 1 en
may diverge globally convergent simple root double root simple root
22 en+1 ⇠ Cen
en+1 ⇠ 1 en 2
en+1 ⇠ Ce1.618 n

Numerical Methods & Scientific Computing: lecture notes
Root-finding
Hybrid methods
Attractive to combine global convergence of bisection with speed of another method e.g. Newton or secant
! hybrid methods that switch between basic methods such that interval is always bracketing
Example
MATLAB’s fzero
switches between bisection, secant and Inverse Quadratic Interpolation (faster than secant)
needs no derivative

Numerical Methods & Scientific Computing: lecture notes
Root-finding
What about systems of nonlinear equations?
Try Newton’s Method for system of 2 equations in 2 variables.
f(x,y)=0 g(x,y)=0
Expand in Taylor series about current iterate to get tangent plane
approximation:
f(xn+1,yn+1)⇡f(xn,yn)+ @f |n (xn+1 xn)+ @f |n (yn+1 yn) = 0
g(xn+1,yn+1)⇡g(xn,yn)+@g |n (xn+1xn)+@g |n (yn+1yn) = 0 @x @y
@x @y

Numerical Methods & Scientific Computing: lecture notes
Root-finding
or in matrix notation
f(x,y)”@f|n @f|n#x x0
nn+@x@y n+1n= g(xn,yn) @g |n @g |n yn+1 yn 0
@x @y
where partial derivs are evaluated at (xn,yn)
=) at each iteration. must solve a linear system of the form J |n (xn+1 xn) = f |n
=) must learn how to solve linear systems first!

Numerical Methods & Scientific Computing: lecture notes
Root-finding
End of Lecture 10