Roots of Equations I

Outline
• Introduction
• Bracketing Methods
• Bisection Method
• Regula-Falsi Method
Introduction
• In Algebra we learned how to solve for the roots (also known as zeros
or solutions) to equations.
• These are the values of 𝑥 such that the value of the function is zero.
𝑓 𝑥 =0
Introduction
• For linear equations, we learned that we can simply use algebraic
manipulation.
𝑓 𝑥 = 𝑎𝑥 + 𝑏 = 0
𝑎𝑥 = −𝑏
𝑥 = −𝑏/𝑎
Introduction
• For quadratic equations, we learned how solve these using different
methods such as factoring, completing the square, and the quadratic
formula
𝑓 𝑥 = 𝑎𝑥2 + 𝑏𝑥 + 𝑐 = 0
−𝑏 ± 𝑏2 − 4𝑎𝑐
𝑥=
2𝑎
Introduction
• How about the much more difficult nonlinear equations? We were
taught to use algebraic manipulation, together with laws of
exponents, properties of logarithms, and other methods so we can
isolate the variable in one side of the equation.
• However, there are equations where this method is difficult. As an
alternative, we can solve them using numerical root-finding methods.
 • The discriminant (𝑫) of the quadratic equation
𝑎𝑥 2 + 𝑏𝑥 + 𝑐 is
𝐷 = 𝑏2 − 4𝑎𝑐
Recall: • This is also the expression inside the square root of
the quadratic formula
Nature of 𝑥=
−𝑏 ± 𝑏2 − 4𝑎𝑐
2𝑎
Solutions of • The nature of the roots of quadratic equations can
be determined from this number.
Quadratic • If 𝒃𝟐 − 𝟒𝒂𝒄 > 𝟎, there are two distinct real
roots;
Equations • If 𝒃𝟐 − 𝟒𝒂𝒄 = 𝟎, there is one distinct real
roots;
• If 𝒃𝟐 − 𝟒𝒂𝒄 < 𝟎, there are no real roots
(imaginary).
Introduction
• Nature of solutions of an equation can be
• Finite or infinite in number
• Examples: linear equation vs trigonometric equation
• Can be further classified as
• Real and distinct
• Real and repeating
• Complex conjugates
• Combination of these
Introduction
Introduction
Introduction
Introduction
Introduction
Introduction
• We have the bracketing methods and open methods to find the real
roots of a function 𝑓(𝑥).
• In this course, we will only tackle the following basic methods:
• Bracketing Methods
• Bisection Method
• Regula-Falsi Method
• Open Methods
• Fixed-Point Iteration
• Newton-Raphson Method
Bracketing Methods
• Some information about bracketing methods:
• Need to know an interval (lower and upper bound) where to look for a root.
• The function must be continuous within the interval.
• Will have problems if there are multiple roots in the chosen interval.
• Cannot identify a root that does not cross (tangent to) the 𝑥-axis.
• Cannot distinguish between a root and a singularity point.
• Convergence for these methods is relatively slow.
Bisection Method
• Bisection Method – also known
as interval halving
• Simple, safe, and very robust
• If 𝑓(𝑥) is real and continuous on
the interval [𝑎, 𝑏], and 𝒇(𝒂) and
𝒇(𝒃) have opposite signs or in
other words their product is a
negative
𝑓 𝑎 ⋅𝑓 𝑏 <0
• then there is at least one real
root between 𝒂 and 𝒃.
Bisection Method
1. Turn the equation to a function of the variable we want to solve
such that 𝑓 𝑥 = 0.
2. Find an interval [𝒂, 𝒃] where a zero of the function exists.
3. Find the midpoint of the interval [𝒂, 𝒃]. Let’s call it 𝒄. Set 𝑐 = 𝑎+𝑏.
2
Find the function values at all 3 points, 𝒇 𝒂 , 𝒇 𝒃 , 𝒇(𝒄).
4. If 𝒇(𝒄) is zero, then 𝒄 is our root.
5. Split the interval into [𝒂, 𝒄] and [𝒄, 𝒃].
• If 𝒇 𝒂 ∙ 𝒇 𝒄 < 𝟎, new interval becomes [𝒂, 𝒄]. Set 𝒃 = 𝒄.
• If 𝒇 𝒄 ∙ 𝒇 𝒃 < 𝟎, new interval becomes [𝒄, 𝒃]. Set 𝒂 = 𝒄.
Bisection Method
6. Identify the exit criterion and set a tolerance then repeat steps 3-5
until the solution converges.
7. The answer is 𝒄 upon convergence.
Bisection Method
• Example: Solve for 𝑥 in 𝑥 2 + 2 = 2𝑥
1. Turn the equation to a function of the variable we want to solve
such that 𝑓 𝑥 = 0.
𝑥 2 + 2 = 2𝑥
2𝑥 − 𝑥2 − 2 = 0
𝑓 𝑥 =0
𝑓 𝑥 = 2𝑥 − 𝑥2 − 2
Bisection Method
• Example: Solve for 𝑥 in 𝑥 2 + 2 = 2𝑥
𝑓 𝑥 = 2𝑥 − 𝑥2 − 2
2. Find an interval [𝒂, 𝒃] where a zero of the function exists.
• You can think of this as the interval where the sign of the function changes
from negative to positive or positive to negative.
• The smaller the interval, the faster it will converge.
𝑓 3 = 23 − 32 − 2 = 8 − 9 − 2 = −3
𝑓 4 = 24 − 42 − 2 = 16 − 16 − 2 = −2
𝑓 5 = 25 − 52 − 2 = 32 − 25 − 2 = 5
𝑓 6 = 26 − 62 − 2 = 64 − 36 − 2 = 26
• We can use the interval [𝟒, 𝟓].
Bisection Method
• Example: Solve for 𝑥 in 𝑥 2 + 2 = 2𝑥
𝑓 𝑥 = 2𝑥 − 𝑥2 − 2; interval[𝟒, 𝟓]
3. Find the midpoint of the interval [𝒂, 𝒃]. Let’s call it 𝒄. Set 𝑐 = 𝑎+𝑏.
2
Find the function values at all 3 points, 𝒇 𝒂 , 𝒇 𝒃 , 𝒇(𝒄).
• 𝑎 = 4; 𝑓 4 = −2
• 𝑏 = 5; 𝑓 5 =5
𝑎+𝑏 4+5 9
•𝑐= = = = 4.5; 𝑓 4.5 = 0.377417
2 2 2
Bisection Method
• Example: Solve for 𝑥 in 𝑥 2 + 2 = 2𝑥
𝑓 𝑥 = 2𝑥 − 𝑥2 − 2; interval 𝟒, 𝟓 ; midpoint 𝟒. 𝟓
4. If 𝒇(𝒄) is zero, then 𝒄 is our root.
• 𝑓 4.5 = 0.377417, which is not zero, 𝟒. 𝟓 is not our root.
Bisection Method
• Example: Solve for 𝑥 in 𝑥 2 + 2 = 2𝑥
𝑓 𝑥 = 2𝑥 − 𝑥2 − 2; interval 𝟒, 𝟓 ; midpoint 𝟒. 𝟓
5. Split the interval into [𝒂, 𝒄] and [𝒄, 𝒃].
• If 𝒇 𝒂 ∙ 𝒇 𝒄 < 𝟎, new interval becomes [𝒂, 𝒄]. Set 𝒃 = 𝒄.
• If 𝒇 𝒄 ∙ 𝒇 𝒃 < 𝟎, new interval becomes [𝒄, 𝒃]. Set 𝒂 = 𝒄.
𝑓 4 ⋅ 𝑓 4.5 = −2 ⋅ 0.377417 = −0.754833996 < 0
𝑓 4.5 ⋅ 𝑓 5 = 0.377417 ⋅ 5 = 1.88708499 > 0
Set 𝑏 = 4.5. New interval [𝟒, 𝟒. 𝟓]
Bisection Method
• Example: Solve for 𝑥 in 𝑥 2 + 2 = 2𝑥
𝑓 𝑥 = 2𝑥 − 𝑥 2 − 2; interval 𝟒, 𝟒. 𝟓
6. Identify the exit criterion and set a tolerance then repeat steps 3-5
until the solution converges.
• For root-finding methods, all of the 𝐿𝑝 exit criterion will reduce to just the
absolute value of the difference of the new and old value since we are only
looking at one difference. This criterion is more appropriate to use with
iterations on matrices.
• Let’s use the approximate error as the exit criterion.
• Set a tolerance value of 0.001. 𝑡𝑜𝑙 = 1𝑒 − 3
𝑐 − 𝑐𝑜𝑙𝑑
If < 𝑡𝑜𝑙, stop the iteration
𝑐
Bisection Method
• Example: Solve for 𝑥 in 𝑥 2 + 2 = 2𝑥
𝑓 𝑥 = 2𝑥 − 𝑥2 − 2
7. The answer is 𝒄 upon convergence.
𝒄 = 𝟒. 𝟒𝟒𝟏𝟒𝟎𝟔
Regula-Falsi Method
• Regula-Falsi Method – also
known as false position
method
• Similar to bisection method,
but instead of continuously
bisecting the interval, the
linear interpolation concept
is used.
• Success depends on the
initial guesses and shape of
the curve.
Regula-Falsi Method
1. Turn the equation to a function of the variable we want to solve
such that 𝑓 𝑥 = 0.
2. Find an interval [𝒂, 𝒃] where a zero of the function exists.
𝑓 𝑏 ⋅(𝑏−𝑎)
3. Find the midpoint, 𝒄, of the interval [𝒂, 𝒃]. Set 𝑐 = 𝑏 − .
𝑓 𝑏 −𝑓(𝑎)
Find the function values at all 3 points, 𝒇 𝒂 , 𝒇 𝒃 , 𝒇(𝒄).
4. If 𝒇(𝒄) is zero, then 𝒄 is our root.
5. Split the interval into [𝒂, 𝒄] and [𝒄, 𝒃].
• If 𝒇 𝒂 ∙ 𝒇 𝒄 < 𝟎, new interval becomes [𝒂, 𝒄]. Set 𝒃 = 𝒄.
• If 𝒇 𝒄 ∙ 𝒇 𝒃 < 𝟎, new interval becomes [𝒄, 𝒃]. Set 𝒂 = 𝒄.
Regula-Falsi Method
6. Identify the exit criterion and set a tolerance then repeat steps 3-5
until the solution converges.
7. The answer is 𝒄 upon convergence.
Regula-Falsi Method
• Example: Solve for 𝑥 in 𝑥 2 + 2 = 2𝑥
1. Turn the equation to a function of the variable we want to solve
such that 𝑓 𝑥 = 0.
𝑥 2 + 2 = 2𝑥
2𝑥 − 𝑥2 − 2 = 0
𝑓 𝑥 =0
𝑓 𝑥 = 2𝑥 − 𝑥2 − 2
Regula-Falsi Method
• Example: Solve for 𝑥 in 𝑥 2 + 2 = 2𝑥
𝑓 𝑥 = 2𝑥 − 𝑥2 − 2
2. Find an interval [𝒂, 𝒃] where a zero of the function exists.
• You can think of this as the interval where the sign of the function changes
from negative to positive or positive to negative.
• The smaller the interval, the faster it will converge.
𝑓 3 = 23 − 32 − 2 = 8 − 9 − 2 = −3
𝑓 4 = 24 − 42 − 2 = 16 − 16 − 2 = −2
𝑓 5 = 25 − 52 − 2 = 32 − 25 − 2 = 5
𝑓 6 = 26 − 62 − 2 = 64 − 36 − 2 = 26
• We can use the interval [𝟒, 𝟓].
Regula-Falsi Method
• Example: Solve for 𝑥 in 𝑥 2 + 2 = 2𝑥
𝑓 𝑥 = 2𝑥 − 𝑥2 − 2; interval[𝟒, 𝟓]
𝑓 𝑏 ⋅(𝑏−𝑎)
3. Find the midpoint, 𝒄, of the interval [𝒂, 𝒃]. Set 𝑐 = 𝑏 − .
𝑓 𝑏 −𝑓(𝑎)
Find the function values at all 3 points, 𝒇 𝒂 , 𝒇 𝒃 , 𝒇(𝒄).
• 𝑎 = 4; 𝑓 4 = −2
• 𝑏 = 5; 𝑓 5 = 5
• 𝑐 = 𝑏 − 𝑓 𝑏 ⋅ 𝑏−𝑎 = 5 − 5 ⋅ 5−4 5
= 5 − = 4.285714;
𝑓 𝑏 −𝑓 𝑎 5 − −2 7
• 𝑓 4.285714 = −0.86313
Regula-Falsi Method
• Example: Solve for 𝑥 in 𝑥 2 + 2 = 2𝑥
𝑓 𝑥 = 2𝑥 − 𝑥2 − 2; interval 𝟒, 𝟓 ; c = 4.285714
4. If 𝒇(𝒄) is zero, then 𝒄 is our root.
• 𝑓 4.285714 = −0.86313, which is not zero, 4.285714 is not our root.
Regula-Falsi Method
• Example: Solve for 𝑥 in 𝑥 2 + 2 = 2𝑥
𝑓 𝑥 = 2𝑥 − 𝑥2 − 2; interval 𝟒, 𝟓 ; c = 4.285714
5. Split the interval into [𝒂, 𝒄] and [𝒄, 𝒃].
• If 𝒇 𝒂 ∙ 𝒇 𝒄 < 𝟎, new interval becomes [𝒂, 𝒄]. Set 𝒃 = 𝒄.
• If 𝒇 𝒄 ∙ 𝒇 𝒃 < 𝟎, new interval becomes [𝒄, 𝒃]. Set 𝒂 = 𝒄.
𝑓 4 ⋅ 𝑓 4.285714 = −2 ⋅ −0.86313 = 1.726257 > 0
𝑓 4.285714 ⋅ 𝑓 5 = −0.86313 ⋅ 5 = −4.31564 < 0
Set 𝑎 = 4.285714. New interval [4.285714, 𝟓]
Regula-Falsi Method
• Example: Solve for 𝑥 in 𝑥 2 + 2 = 2𝑥
𝑓 𝑥 = 2𝑥 − 𝑥2 − 2; interval 4.285714, 𝟓
6. Identify the exit criterion and set a tolerance then repeat steps 3-5
until the solution converges.
• Let’s use the approximate error as the exit criterion.
• Set a tolerance value of 0.001. 𝑡𝑜𝑙 = 1𝑒 − 3
𝑐 − 𝑐𝑜𝑙𝑑
If < 𝑡𝑜𝑙, stop the iteration
𝑐
Regula-Falsi Method
• Example: Solve for 𝑥 in 𝑥 2 + 2 = 2𝑥
𝑓 𝑥 = 2𝑥 − 𝑥2 − 2
7. The answer is 𝒄 upon convergence.
𝒄 = 𝟒. 𝟒𝟑𝟗𝟕𝟓𝟒
Regula-Falsi Method
• Example: Solve for 𝑥 in 𝑥 2 + 2 = 2𝑥
𝑓 𝑥 = 2𝑥 − 𝑥2 − 2
7. The answer is 𝒄 upon convergence.
𝒄 = 𝟒. 𝟒𝟑𝟗𝟕𝟓𝟒
Assignment
1. Let your Student ID be 20𝑥𝑦 − 𝑎𝑏𝑐𝑑𝑒𝑓.
• Let 𝑝 = 10𝑎 + 𝑏; 𝑞 = 10𝑐 + 𝑑; 𝑟 = 10𝑒 + 𝑓.
• Find the zero of the following function:
ℎ 𝑥 = 𝑝𝑥2 − 𝑞𝑥 − 𝑟
• Use the approximate error as the exit criterion with a tolerance of 0.01
• If 𝒇 is an even number, use regula-falsi method
• If 𝒇 is an odd number, use bisection method
Assignment
2. Determine the drag coefficient 𝑐𝑑 needed for a parachutist of mass 𝑚 = 68.1 𝑘𝑔
to have a velocity of 40 𝑚/𝑠 after free-falling for time 𝑡 = 10 𝑠. Assume the
acceleration due to gravity is 9.8 𝑚/𝑠2.
𝑔𝑚 − 𝑐𝑑 𝑡
𝑣 𝑡 = 1−𝑒 𝑚
𝑐𝑑
• Use the approximate error as the exit criterion with a tolerance of 𝟎. 𝟎𝟎𝟏
• If the last digit of your Student ID is an even number, use bisection method
• If the last digit of your Student ID is an odd number, use regula-falsi method
• For your solution, show only the first round of calculations, and then a table of all
the values, then your final answer. Make sure to box your final answer with the
correct units. (20 points)
Any questions?