Newton's Method - Finding Complex Roots

[doll parts]

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:

#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:

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!

[ddanbe]

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

[iamthwee]

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

[tex]x^3-x = 0[/tex]

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...

[ArkM]

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:

typedef complex<double> Complex;

[DavidB]

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).

[iamthwee]

>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

[dougy83]

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:

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.

[DavidB]

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).

[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

[ithelp]

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.

[huss_584]

Thank you, if possible by simple Java code