Motivation Roots of Equations Direct Search, Bisection Methods Regula Falsi, Secant Methods Newton-Raphson Method Zeros of Polynomials (Horner s, Mull

(1)

Roots of Equations

Direct Search, Bisection Methods

Regula Falsi, Secant Methods

Newton-Raphson Method

Zeros of Polynomials (Horner’s, Muller’s methods)

EigenValue Analysis

ITCS 4133/5133: Introduction to Numerical Methods 1 Roots of Equations

Motivation

Solution to many scientific and engineering problems

Equations may be non-linear

Equations expressible in the formF (x) = 0

Values ofxthat satisfy the above equation are termed“roots”

Example:Quadratic Equation ax2_{+ bx + c = 0} with roots x1 = −b + √ b2_{− 4ac} 2a x2 = −b − √ b2_{− 4ac} 2a

Example Functions

Direct Search Method

Trial and Error Approach: Evaluatef(x)over some range ofxat multiple points

Specify a range within which the root is assumed to occur

Subdivide range into smaller, uniformly spaced intervals

Search through all subintervals to locate the root.

(2)

Direct Search:Searhing an interval

Evaluate at end points of interval, and check iff(x) has opposite polarity.

Direct Search:Disadvantages

⇒ Computationally expensive (linear search)

⇒ Intervals have to be very small, for high precision

⇒ If intervals are too large, roots can be missed.

⇒ Multiple roots cannot be handled:

f(x) = x2_{− 2x + 1}

Bisection Method

Assumes a single root within the interval of interest.

Similar to binary search: evaluates function at middle of interval and moves to interval containing the root.

Requires fewer calculations than direct search method.

Bisection Method:Algorithm

(3)

Bisection Method:Example

Error Analysis

Error measures can be an absolute value,

d= |xm,i+1− xm,i| or, a percent error

r= xm,i+1− xm,i xm,i+1 100

True Accuracy is known only if true solution (rootxt) is known

r= xt− xm,i xt 100

Regula Falsi,Secant Methods

Bisection makes no use of shape of function to determine root.

Use a straightline approximation tof(x)(in contrast to the midpoint) to find the approximate root location.

Start with 2 points,(a, f(a)), (b, f(b))that satisfies(f(a).f(b) < 0.

Regula Falsi Method

Next approximation: where the straightline approximation crosses the x-axis: f(b) (b − s) = f(b) − f(a) (b − a) s = b − b − a f(b) − f(a)f(b)

(4)

Regular Falsi: Algorithm

Regular Falsi: Example(Cube Root of 2)

Secant Method

Similar to Regula Falsi method, with a slight modification.

New estimate ofxi+1of the root, based onf(xi)andf(xi−1)

Especially useful when its difficult to obtain derivatives analytically.

x2= x1−x_y1− x0 1− y0y1 and

xi+1= xi−x_yi− xi−1 i− yi−1yi

Secant Method (contd)

f(xi−1)

xi+1− xi−1 =

f(xi)

xi+1− xi Solving forxi+1gives

xi+1 = xi−f(x_f(xi)[xi−1− xi] i−1− f(xi) = xi−_f(xf(x_i−1_−f(xi) _i₎ xi−1−xi = xi−_ff(x0_(xi) i) which is similar in form to the Newton’s method.

⇒ Secant method doesnt require testing for interval selection

⇒ Generally converges faster, but not guaranteed.

(5)

Secant Method:Algorithm

Secant Method:Example(Square Root of 2)

Newton-Raphson Method

Motivation: Rate of convergence of bisection method is slow.

Newton’s iteration method uses thelinearportion of the Taylor series

f(x1) = f(x0) +_dxdf∆x where∆x = x1− x0,_dxdf is the derivative w.r.tx.

f(x1) = 0 = f(x0) +_dxdf(x1− x0) whenx1is the root of the function.

x1= x0−_df/dxf(x0) = x0−_ff(x0_(x0)

0)(derivativef

0_{evaluated at}_x 0)

Newton-Raphson Method (contd)

Iteratively,

xi+1= xi−_ff(x0_(xi) i)

Accuracy

Iff(x)is linear, first iteration produces exact solution

If f(x) is non-linear, accuracy depends on importance of the trun-cated non-linear terms of the Taylor series

Graphical Interpretation Approximatef0_(x i)over[xi, xi+1]as f0_(x i) = f(x_x i− 0) i+1− xi from which the iteration is derived.

(6)

Newton-Raphson Method: Algorithm

Newton-Raphson Method: Example

Newton-Raphson Method:Non-Convergence

f0_(x)_{approaches zero, exception (division by zero).}

Solutionoscillatesbetween two different solutions

f(xi)/f0(xi) = −f(xi+1/f0(xi+1)

Solving Non-Linear Equations

Addresses root finding to two or more variables

Approach: Solve for the variables and aJacobistyle iteration tech-nique

Example

x3_{− 3x}2_{+ xy = 0}

4x2_{− 4xy}2_{+ 3y}2 _{= 0} Solve forxandy,

x = (3x2_{− xy)}1/3

y = 4x2_4x+ 3y21/2

Use initial estimates for x and y to begin the iteration using most recent values ofxandy.

(7)

Muller’s Method

Extension of theSecant Method; uses a quadratic approximation.

Starts with 3 initial approximationsx0, x1, x2 and consider the next approximation x4 as the intersection of the parabola connecting

(x0, f(x0)), (x1, f(x1)), (x2, f(x2))with thex-axis

In general, less sensitive to starting values than Newton’s method.

Muller’s Method(contd)

Start with

P (x) = a(x − x2)2+ b(x − x2) + c

As the quadratic passes through(x0, f(x0)),(x1, f(x1)and(x2, f(x2)

f(x0) = a(x0− x2)2+ b(x0− x2) + c

f(x1) = a(x1− x2)2+ b(x1− x2) + c

f(x2) = a.02+ b.0 + c = c We can solve fora, b, c

a = (x1− x2)[f(x_(x0) − f(x2)] − (x0− x2)[f(x1) − f(x2)]

0− x2)(x1− x2)(x0− x1)

b = (x0− x2)2[f(x1) − f(x2)] − (x1− x2)2[f(x0) − f(x2)] (x0− x2)(x1− x2)(x0− x1)

c = f(x2)

Muller’s Method (contd.)

We can solve the quadraticP (x)for the next estimate,x3.

P (x) = P (x3− x2) = a(x3− x2)2+ b(x3− x2) + c = 0 resulting in x3− x2= −b ± √ b2_{− 4ac} 2a

The above form can cause roundoff errors, when b2 _{≫ 4ac}_{. Instead} use

x3− x2 = −2c

b ±√b2_{− 4ac}

Muller’s method chooses the root, that agrees with the sign ofbto make the denominator large, and hence closest root tox2.

Eigenvalue Analysis

Eigen values, denoted byλ, are values for the matrix system

[A − λI]X = 0

having a non-zero solution vectorX.

⇒ AandIaren × n ⇒ Iis the identity matrix.

⇒ Applications: Analysis of sediment deposits in river beds, analyzing flutter in airplane wings.

Solve

|A − λI| = 0

resulting in annth order polynomial, to be solved for theλs.

(8)

Eigenvalue Analysis(contd.)

For a3 × 3system, |A − λI| = a11− λ a12 a13 a21 a22− λ a23 a31 a32 a33− λ = 0 resulting in λ3_{+ b} 2λ2+ b1λ + b0= 0

Analyis: Root Finding Methods

Need to understanderrors

Need to understancdconvergence rates

Convergence Rate

If|en+1|approachesK ∗ |en|pas=⇒ ∞,then the method is of orderp

Typically convergence rates are valid only close to the root.

Can study convergence rates experimentally or theoretically.

Convergence Rate: Fixed Point Iteration

xn+1= g(xn)

Ifx = ris a solution off(x) = 0, thenf(r) = 0, r = g(r). Thus,

xn+1− r = g(xn) − g(r) = g(x_(xn) − g(r)

n− r) (xn− r)

We can use the mean value theorm (assumingg(x), g0_(x)_{are continuous)}

xn+1− r = g0(ξn) ∗ (xn− r) whereξn ∈ (xn, r). Similarly, the error can be defined as

ei+1= g0(ξn) ∗ ei

Convergence Rate: Fixed Point Iteration

|ei+1| = |g0(ξn)| ∗ |ei|

Suppose|g0_{(x)| < K < 1}_{for all} _{x ∈ (r − h, r + h)}_{, then if}_x

0 is in this interval, then the iterates converge, as

|en+1| < K ∗ |en| < K2∗ |en−1| < K3|en−2| < .... < Kn+1∗ |e0| which impliesfixed point iteration is of order 1.

(9)

Convergence Rate: Newton’s Method

xn+1= xn−_ff(x₀_(xn)

n) = g(xn)

◦ Has the same form as the fixed point iteration.

◦ Thus, successive iterates converge if|g0_{(x)| < 1} Assume a simple root atx = r,

g0_{(x) = 1 −}f0(x) ∗ f0(x) − f(x) ∗ f00(x) [f0_(x)]2 = f(x) ∗ f00_(x) [f0_(x)]2 Thus, if f(x) ∗ f00_(x) [f0_(x)]2 < 1

in an interval around the rootr, the method will converge for anyx0.

Convergence Rate: Newton’s Method

Ifris a root off(x) = 0, thenr = g(r), xn+1= g(xn), so

xn+1− r = g(xn) − g(r)

Expandingg(xn)using Taylor series, expanding about(xn− r),

g(xn) = g(r) + g0(r) ∗ (xn− r) +g 00_(ξ) 2 (xn− r)2 withξ ∈ (xn, r) g0_{(r) =}f(r) ∗ f00(r) [f0_(r)]2 = 0 thus g(xn) = g(r) +g 00_(ξ) 2 (xn− r)2

Convergence Rate: Newton’s Method

g(xn) = g(r) +g 00_(ξ) 2 (xn− r)2 Ifxn− r = en, we have en+1= xn+1− r = g(xn) − g(r) = g 00_(ξ) 2 en2

Thus, each error in the limit is proportional to the second power of the previous error, resulting convergence of order 2, or quadratic convergence.

Convergence Rate: Bisection Method

Method based on intermediate valuetheorem: root exists in the interval

[a, b], iff(a)andf(b)are of opposite sign.

Error at stagekis at most(b − a)/2k

Error estimates(on the average) are reduced by half at each iteration

|en+1| = 0.5 ∗ |en|

Bisection is linearly convergent.

(10)

Analysis: Regula Falsi, Secant Methods

Rate of Convergence:Must investigate

|xk− x∗|

|xk−1− x∗|p for large values ofp.

It can be shown that errors are reduced as follows:

en+1= g 00_(ξ

i, ξ2)

2 (en)en−1 Convergence rate can be shown to be about 1.62.