Numworks: Quadratic Equation and Newton's Method - Do Guesses Matter?
Introduction
Let A, B, C, be positive, non-zero coefficients of the quadratic equation:
Ax^2 + Bx - C = 0 with A > 0, B > 0, C > 0
First, start with an initial guess x0 = 0. Count how many iterations it takes for the method to reach a suitable answer. For this experiment, we will use a tolerance of 8 decimal places (tol = 1E-8), setting a maximum of 200 iterations.
Consider a "reduced" equation to obtain guesses for the original equation:
Ax^2 - C = 0
Hence, our initial guesses are x0 = √(C/A) and x0 = -√(C/A)
Using Newton's Method to determine the roots with a guess of x0:
x_n+1 = x_n - [Ax^2 + Bx - C]/[2Ax + B]
So which of the following guesses gets us to a solution faster?
x0 = 0
x0 = √(C/A)
x0 = -√(C/A)
The Python script below tests the question.
Python Test Script: guesttest.py
from math import *
def testf(a,b,c,w0):
n=1
w1=1
while abs(w1)>1e-8
w1=(a*w0**2+b*w0-c)/(2*a*w0+b)
w0=w0-w1
n=n+1
if n==201:
print('Exceeded iterations')
break
print('Root: '+str(w0)
print('Iterations: '+str(n))
return
# EWS 2020-08-10
print("y=ax**2+bx-c=0")
print("a>0,b>0,c>0")
a=float(input('a? '))
b=float(input('b? '))
c=float(input('c? '))
# initial conditions
x1=0
x2=sqrt(c/a)
x3=-sqrt(c/a)
# results
print('x1: '+str(x1))
testf(a,b,c,x1)
print('----')
print('x2: '+str(x2))
testf(a,b,c,x2)
print('----')
print('x3: '+str(x3))
testf(a,b,c,x3)
print('----')
Results
Test Results - Iterations Used to get to a Solution
Ax^2 + Bx - C = 0 with A > 0, B > 0, C > 0
| A | B | C | x0 = 0 | x0 = √(C/A) | x0 =-√(C/A) |
|---|---|---|---|---|---|
| 1 | 1 | 4 | 6 | 6 | 8 |
| 1 | 4 | 4 | 6 | 6 | error reached |
| 1 | 5 | 4 | 6 | 6 | 9 |
| 1 | 5 | 6 | 6 | 6 | 12 |
| 2 | 5 | 6 | 6 | 6 | 8 |
| 3 | 5 | 6 | 7 | 6 | 7 |
| 8 | 13 | 81 | 8 | 6 | 6 |
| 16 | 13 | 81 | 8 | 5 | 6 |
| 32 | 13 | 81 | 9 | 5 | 5 |
| 64 | 13 | 81 | 9 | 5 | 5 |
| 1 | 40 | 10 | 5 | 6 | 6 |
| 1 | 40 | 25 | 5 | 6 | 6 |
| 1 | 40 | 40 | 5 | 6 | 7 |
| 1 | 40 | 55 | 6 | 6 | 8 |
| 10 | 18 | 42 | 7 | 6 | 7 |
| 10 | 18 | 52 | 7 | 6 | 6 |
| 10 | 18 | 62 | 7 | 6 | 6 |
| 10 | 18 | 72 | 7 | 6 | 6 |