Sunday, August 30, 2020

Numworks: Quadratic Equation and Newton's Method - Do Guesses Matter?

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

From the data presented, I think it is inconclusive of whether which guess generally makes for getting to the solution faster.   What do you find?  

Eddie 

All original content copyright, © 2011-2020.  Edward Shore.   Unauthorized use and/or unauthorized distribution for commercial purposes without express and written permission from the author is strictly prohibited.  This blog entry may be distributed for noncommercial purposes, provided that full credit is given to the author.