[go: up one dir, main page]
Scribd
Upload
96 views14 pages

ESO 208A: Computational Methods in Engineering: Department of Civil Engineering IIT Kanpur

This document discusses numerical methods for finding the roots of nonlinear equations, including the secant method and Muller's method. The secant method approximates the tangent line with a secant line to overcome the disadvantage of needing to calculate derivatives. Muller's method fits a quadratic polynomial through three points to approximate the function and find its root. Both methods iteratively find better approximations that converge quadratically to the root.

Uploaded by

Jainam
Copyright
© © All Rights Reserved
We take content rights seriously. If you suspect this is your content, claim it here.
Available Formats
Download as PDF, TXT or read online on Scribd
96 views14 pages

ESO 208A: Computational Methods in Engineering: Department of Civil Engineering IIT Kanpur

This document discusses numerical methods for finding the roots of nonlinear equations, including the secant method and Muller's method. The secant method approximates the tangent line with a secant line to overcome the disadvantage of needing to calculate derivatives. Muller's method fits a quadratic polynomial through three points to approximate the function and find its root. Both methods iteratively find better approximations that converge quadratically to the root.

Uploaded by

Jainam
Copyright
© © All Rights Reserved
We take content rights seriously. If you suspect this is your content, claim it here.
Available Formats
Download as PDF, TXT or read online on Scribd
You are on page 1/ 14

ESO 208A: Computational

Methods in Engineering
Arghya Das

Department of Civil Engineering


IIT Kanpur
Roots of Nonlinear
Equations
Open Methods: Secant
 Principle: Use a difference approximation for the slope
or derivative in the Newton-Raphson method. This is
equivalent to approximating the tangent with a secant.
 Problem: f(x) = 0, find a root x = α such that f(α) = 0

f(x0)

f(x1)
f(x2)
x0 x1 x2
y = f(x)
x3 24
Open Methods: Secant
 Problem: f(x) = 0, find a root x = α such that f(α) = 0

 Initialize: choose two points x0 and x1 and evaluate f(x0) and f(x1)

 Approximation: , replace in Newton-


Raphson

 Iteration Formula:

 Stopping criteria:

25
Open Methods: Secant

Advantages:

Fast convergence
(slightly less than
y = f(x)
quadratic) f(x0)
x1
Overcomes the x0
disadvantage of having f(x1)
to calculate derivate

Secant method may


also get stuck!
26
Open Methods: Secant
 Convergence: Newton’s polynomial,
0=𝑓 𝛼 =𝑓 𝑥 + 𝛼 − 𝑥 𝑓 𝑥 ,𝑥 + 𝛼−𝑥 𝛼−𝑥 𝑓 𝜉

for some 𝜉 ∈ 𝑥 ,𝑥 ,𝛼

Divided difference:

 Re-arrange:

, ,

[using mean value theorem]

 As , = constant

27
Open Methods: Secant
 Derivative of the Newton-Raphson method
is evaluated numerically using difference
approximation.
 Numerical methods for estimation of
derivative of a function will be covered in
detail later.
 Rest of the method is same.

28
Open Methods: Muller
 Principle: fit a quadratic polynomial through three
points to approximate the function.
 Problem: f(x) = 0, find a root x = α such that f(α) = 0

f(x0)
f(x1)
f(x2)

x0 x1 x2
y = f(x)

x3
29
Open Methods: Muller
 Initialize: choose three points x0, x1, x2 and evaluate f(x0), f(x1),
f(x2). Denote f(xk) = fk
 Fit a quadratic polynomial through three points xk, xk-1, xk-2 as:
p(x) = a(x - xk)2 + b(x - xk) + c
 Equations:
p(xk) = fk = c
p(xk-1) = fk-1 = a(xk-1 - xk)2 + b(xk-1 - xk) + fk
p(xk-2) = fk-2 = a(xk-2 - xk)2 + b(xk-2 - xk) + fk
 Define Divided Differences:
 1st Divided Difference:
, ,
 2nd Divided Difference:
30
Open Methods: Muller
p(xk) = fk = c
p(xk-1) = fk-1 = a(xk-1 - xk)2 + b(xk-1 - xk) + fk
p(xk-2) = fk-2 = a(xk-2 - xk)2 + b(xk-2 - xk) + fk

 Express as:

 Solutions:

31
Properties of Divided Differences
, ,
2nd Divided Difference: 𝑓 𝑥 , 𝑥 ,𝑥 =

32
Note: Properties of Divided Differences
 1st Divided Difference:

 2nd Divided Difference:


, , , , , ,

We shall use these properties for the Theory of Approximation!

33
Open Methods: Muller
 Principle: fit a quadratic polynomial through three points to
approximate the function.
 Problem: f(x) = 0, find a root x = α such that f(α) = 0
 Initialize: choose three points x0, x1, x2 and evaluate f(x0), f(x1), f(x2)
 Fit a quadratic polynomial through three points xk, xk-1, xk-2 as:
p(x) = a(x - xk)2 + b(x - xk) + c
 Constants: c = f(xk); b = f[xk, xk-1] + (xk - xk-1)f[xk, xk-1, xk-2]; a = f[xk,
xk-1, xk-2]
 
±
 Iteration step k: or  
±

 Stopping criteria:
34
Open Methods: Muller
 Convergence: Analysis is similar to Secant method, using
Newton’s Polynomial.

as , = constant

35

You might also like