Nonlinear Equation
Wednesday, October 1, 2014 1:10 PM
===============================================
THREE NONLINEAR EQUATION SOLVERS
============================
BRACKETING
---------------------------------------------
Key Idea
• "Bracketing Methods" = two-point methods to find roots
Theoretical Model in Computing Page 1
• "Bracketing Methods" = two-point methods to find roots
• Two initial guesses (points) on either sides of the root.
○ Given continuous function
• Sign of decides number of roots between them:
○ Same sign
No root Even roots
○ Different sign
One root Odd number of roots
---------------------------------------------
Bisection Method
1. Pick such that they bound the root (Check if )
2. Evaluate
3. Find the next pair of
a.
b.
c.
4.
a.
---------------------------------------------
False-Position Method (Regular-Falsi)
=> Approximate solution by doing linear interpolation between
1. Find such that
Estimate value of root:
Theoretical Model in Computing Page 2
2. Estimate value of root:
3. Replace one of original points (keeping two points on opposite sides of x axis)
a.
b.
c.
4.
============================
OPEN METHODS
---------------------------------------------
Key Idea
• Require only ONE STARTING VALUE or TWO STARTING VALUES (Not necessarily bracket
root)
• Intersection between tangent line and x-axis can be used to estimate root
---------------------------------------------
Simple Fixed-point Iteration
1. Rearrange function so that x (ONLY X) is on the LEFT SIDE of EQUATION
a.
Example:
2. Select an initial value
3. Use to guess to calculate new value of :
*Mechanism*
can be expressed by pair of equations:
•
Theoretical Model in Computing Page 3
•
•
Fixed-point Iteration CONVERGES if
---------------------------------------------
Newton-Raphson Method
*Most widely used method*
*Based on Taylor series expansion*
*Use tangent line*
• Convenient for functions whose derivatives can be evaluated analytically
ITERATION EQUATION:
4 Cases where Newton-Raphson Method exhibits poor convergence
Theoretical Model in Computing Page 4
---------------------------------------------
Secant Method
*Slight variation of Newton's Method*
*Based on secant lines*
• Require two initial estimates of x
○ Need not to change sign between estimates
ITERATION EQUATION
===============================================
EQUATION WITH "MULTIPLE ROOTS"
============================
Theoretical Model in Computing Page 5
============================
THEORY
---------------------------------------------
Multiple Roots
"MULTIPLE ROOT" corresponds to a point where function is TANGENT to x-axis
*Types of multiple roots*
Double Root Triple Root Quadruple Root
---------------------------------------------
Difficulties Involving Multiple Roots
• Function does not change sign at multiple root => CANNOT USE BRACKETING
• => CANNOT USE NEWTON'S and SECANT
============================
SOLUTION TO EQUATION WITH MULTIPLE ROOTS
---------------------------------------------
Multiple Roots Solving Method
1. Set => this function has same roots as original function
2.
3.
4. ITERATION EQUATION:
===============================================
SYSTEMS OF LINEAR EQUATIONS
============================
THEORY
---------------------------------------------
Systems of Linear Equations
• Focus on locating the roots of set of simultaneous equations.
============================
SOLUTION TO SYSTEMS OF LINEAR EQUATIONS
Theoretical Model in Computing Page 6
SOLUTION TO SYSTEMS OF LINEAR EQUATIONS
---------------------------------------------
Fixed-Point Iteration
1. Transform to move SINGLE variable in each equation to left side.
a. Example:
2. Select initial value for x and y
3. Use to calculate new value of x and y:
a.
b.
---------------------------------------------
Newton-Raphson Method
1. Use Taylor series to expand given equations:
a.
b.
2. Let
3. Solve for x and y to find ITERATIVE EQUATIONS:
4.
===============================================
ROOTS OF POLYNOMIALS
============================
THEORY
---------------------------------------------
Number of roots of Polynomials
Given polynomial:
•
•
• Complex roots exist in conjugate pairs
---------------------------------------------
Finding Solution to Polynomials
• bracketing and open methods can be used
• Finding good initial guesses is complicated
• Open methods can be divergent
Theoretical Model in Computing Page 7
• Open methods can be divergent
=> Muller and Bairstow methods
============================
SPECIAL METHODS FOR SOLVING POLYNOMIALS
============================
MULLER METHOD
---------------------------------------------
Mechanism
• Iteratively find root estimates
• Projecting a PARABOLA to x-axis through THREE FUNCTION VALUES
---------------------------------------------
Process
1. Select three values to project parabola
2. Calculate coefficients of parabola
3. Estimate the root with ITERATIVE EQUATION:
4. Calculate relative error:
5. Repeat the process:
a. If only real roots are being located: , repeat
============================
BAIRSTOW'S METHOD
---------------------------------------------
Mechanism
• ITERATIVE method
• Find both real and complex roots of polynomial
• Based on LONG DIVISION of required polynomial with quadratic function
Newton's method is used to estimate the correct factor of quadratic function
Theoretical Model in Computing Page 8
○ Newton's method is used to estimate the correct factor of quadratic function
---------------------------------------------
Process
Given Polynomial (Dividend)
Quadratic Function (Divisor)
Result (Quotient)
Remainder
Bairstow method = ESTIMATE so that
In each iteration, we find by solving a linear equation
*Numbers to calculate at each iteration*
*Stop condition*
When , iteration is stopped.
*Determine root of *
might have MORE roots than these two:
•
•
•
Theoretical Model in Computing Page 9
