DaniWeb Forum Index > Software Development > C++

Newton's Method - Finding Complex Roots

Please support our C++ advertiser: Intel Parallel Studio Home

•

Join Date: Nov 2008

Posts: 1

Reputation: doll parts is an unknown quantity at this point

Solved Threads: 0

doll parts doll parts is offline

Offline

Newbie Poster

Newton's Method - Finding Complex Roots

Nov 2nd, 2008

Hello. I am having problems with a program I've written to find the roots of a cubic equation using Newton's Method. The user inputs the coefficients in the expression (real) and an initial guess (real or complex), and the program is supposed to return a root of the function. However, my program works very erratically. For instance, I input the equation "x^3 - x = 0" and an initial guess of (1.2, 1.5) and my program returned the root of 0 in 11 iterations. I entered the same equation and guess later without even closing the dos box, and my program returned "In 1000 iterations, no solution was found." It is very rare that my program returns a root, and when it does, it only seems to be able to get the root when it is zero. Any insight would be appreciated.

This is my header file to implement newton's method:

 Help with Code Tags 
 C++ Syntax (Toggle Plain Text) 
#include <iostream>
#include <math.h>
#include <complex>
using namespace std;
 
const int nmax = 1000;
const double error = 1.0e-6;
int n = 1;
double a, b, c, d;
inline complex<double> f(complex<double> x) {return a*x*x*x + b*x*x + c*x + d;}   //cubic polynomial
inline complex<double> fprime(complex<double> x) {return 3.0*a*x*x + 2.0*b*x + c;}//derivative of polynomial
 
complex<double> newton (complex<double>& x)
{ 
	while ((abs(x) > error) && (n < nmax + 1)) 
	{
		x -= (f(x)/fprime(x));
		n++;
	}
	return n;
}
#include <iostream>
#include <math.h>
#include <complex>
using namespace std;

const int nmax = 1000;
const double error = 1.0e-6;
int n = 1;
double a, b, c, d;
inline complex<double> f(complex<double> x) {return a*x*x*x + b*x*x + c*x + d;}   //cubic polynomial
inline complex<double> fprime(complex<double> x) {return 3.0*a*x*x + 2.0*b*x + c;}//derivative of polynomial

complex<double> newton (complex<double>& x)
{ 
	while ((abs(x) > error) && (n < nmax + 1)) 
	{
		x -= (f(x)/fprime(x));
		n++;
	}
	return n;
}

and here is a snippet of code where I implement it:

 Help with Code Tags 
 C++ Syntax (Toggle Plain Text) 
 complex<double> x;
 
	cout << "SOLVING A CUBIC EQUATION ax^3 + bx^2 + cx + d USING NEWTON'S METHOD\n\n";
	cout << "Enter a, b, c, and d.\n\n";
	cin >> a >> b >> c >> d;
 
	cout << "Give an initial approximation to a root.\n";
	cin >> x;
 
	newton(x); // see complex_newton.h
 
	if (n > nmax)
		cout << "In " << nmax << " iterations, no solution was found.\n";
	else
		cout << "The solution is " << x << " and it was found in " << n << " iterations.\n";
 complex<double> x;

	cout << "SOLVING A CUBIC EQUATION ax^3 + bx^2 + cx + d USING NEWTON'S METHOD\n\n";
	cout << "Enter a, b, c, and d.\n\n";
	cin >> a >> b >> c >> d;

	cout << "Give an initial approximation to a root.\n";
	cin >> x;

	newton(x); // see complex_newton.h

	if (n > nmax)
		cout << "In " << nmax << " iterations, no solution was found.\n";
	else
		cout << "The solution is " << x << " and it was found in " << n << " iterations.\n";

Thank you!

•

Join Date: Oct 2008

Posts: 2,015

Reputation: ddanbe has much to be proud of

Solved Threads: 299

ddanbe

Offline

Postaholic

Re: Newton's Method - Finding Complex Roots

Nov 3rd, 2008

I think it has nothing to do with your programmings skills. For this method to work best yo have to have your initial guess, as close as possible to the real root, or the method may fail to converge.
Readall about it in http://en.wikipedia.org/wiki/Newton%27s_method

Today is a gift, that's why it is called "The Present".
Make love, no war. Cave ab homine unius libri.
Danny

•

Join Date: Aug 2005

Posts: 5,273

Reputation: iamthwee is a splendid one to behold

Solved Threads: 378

iamthwee

Offline

Posting Expert

Re: Newton's Method - Finding Complex Roots

Nov 3rd, 2008

Some ppl take it a step further and have the program guess an approximate starting point:

$x^3-x = 0$

By trying values from say x values from -10000 to 10000 and incrementing by 0.01 or something to find where it roughly equals zero.

I haven't thought about complex solutions this is all assuming your code is correct, I haven't bothered to check. I'd try it without complex numbers first...

Last edited by iamthwee; Nov 3rd, 2008 at 6:04 am.

*Voted best profile in the world*

•

Join Date: Jul 2008

Posts: 2,001

Reputation: ArkM has much to be proud of

Solved Threads: 343

ArkM

Offline

Postaholic

Re: Newton's Method - Finding Complex Roots

Nov 3rd, 2008

At first have a look at return n in the newton function

..

Small coin:
1. Add input check up code. If the user type not-a-number you can't detect failed cin state now...
2. Why not while (abs(x) > error && n <= nmax) ?.. Simple and clear...
3. Use typedef for more comfortable coding with templates, for example:

Help with Code Tags

C++ Syntax (Toggle Plain Text)

typedef complex<double> Complex;

Last edited by ArkM; Nov 3rd, 2008 at 6:58 am.

•

Join Date: Jul 2006

Posts: 88

Reputation: DavidB is an unknown quantity at this point

Solved Threads: 2

DavidB

Offline

Junior Poster in Training

Re: Newton's Method - Finding Complex Roots

Nov 3rd, 2008

I don't think Newton's Method can be used to find complex roots. The same goes for the Bisection Method and the Secant Method--all these methods are only applicable for finding roots that you know ahead of time will be real. If you do not know ahead of time that roots will be real, more sophisticated techniques are required, for example, the Companion Matrix technique, Laguerre's Method, or the Jenkins-Traub Method (used on my website, see signature).

Regards.

David
Numerical Mathematical Utilities

•

Join Date: Aug 2005

Posts: 5,273

Reputation: iamthwee is a splendid one to behold

Solved Threads: 378

iamthwee

Offline

Posting Expert

Re: Newton's Method - Finding Complex Roots

Nov 4th, 2008

>I don't think Newton's Method can be used to find complex roots.

Do you have proof that you can't use newton's method for complex roots? I reckon it possible as long as you specify an initial starting point for the complex part of the solution.

"Newton's method also works in the complex numbers; for example, it can be used to find complex roots of polynomials."

http://en.citizendium.org/wiki/Newton's_method

*Voted best profile in the world*

•

Join Date: Jun 2007

Posts: 275

Reputation: dougy83 is on a distinguished road

Solved Threads: 45

dougy83

Offline

Posting Whiz in Training

Re: Newton's Method - Finding Complex Roots

Nov 4th, 2008

As ArkM stated, you don't need to return an integer value as a complex<double> (although you can if it pleases you, of course).

I found the condition in the while() loop a little strange, so I changed it to:

•

Originally Posted by doll parts

Help with Code Tags

C++ Syntax (Toggle Plain Text)
	while ((abs(f(x)) > error) && (n < nmax + 1))
while ((abs(f(x)) > error) && (n < nmax + 1))

That way, when the function f(x) --> 0, the function will quit.

You complained about x = 0 being returned for a^x - x = 0. I'm pretty sure 0 satisfies the equation (as do +/- 1). Anyway, try the above mod and see if it works.

•

Join Date: Jul 2006

Posts: 88

Reputation: DavidB is an unknown quantity at this point

Solved Threads: 2

DavidB

Offline

Junior Poster in Training

Re: Newton's Method - Finding Complex Roots

Nov 8th, 2008

•

Originally Posted by iamthwee

I reckon it possible as long as you specify an initial starting point for the complex part of the solution.

I stand corrected.

Previously, I had only seen Newton's Method covered in sections of textbooks dealing with finding real roots. However, I have since done some further investigating, and found out that Newton's Method can, indeed, be used to find complex roots (as long as the initial guess is complex; otherwise the algorithm would not leave the real axis).

•

Join Date: Oct 2009

Posts: 7

Reputation: huss_584 is an unknown quantity at this point

Solved Threads: 0

huss_584

Offline

Newbie Poster

Oct 14th, 2009

hi please im want from you to solve this qustion

Project 1: Find the root of the function
f(x) = (4+x)^2e^-x = 0
By using
1) Secant Method
2) Newton Method
3) By Accelerated Newton Method

•

Join Date: May 2006

Posts: 1,857

Reputation: ithelp is a name known to all

Solved Threads: 120

ithelp

Offline

Posting Virtuoso

#10

Oct 15th, 2009

•

Originally Posted by huss_584

hi please im want from you to solve this qustion

Project 1: Find the root of the function
f(x) = (4+x)^2e^-x = 0
By using
1) Secant Method
2) Newton Method
3) By Accelerated Newton Method

Take an initial guess and iterate over using while loop (as suggested in the algorithm) unless you get a very close match.