Ad:

C++ Discussion Thread
Unsolved
Views: 11561

Page 1
2
Next

You are currently viewing page 1 of this multi-page discussion thread

Nov 2nd, 2008

Newton's Method - Finding Complex Roots

Expand Post »

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:

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:

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!

doll parts

Reputation Points: 10

Solved Threads: 0

Newbie Poster

Offline

1 posts
since Nov 2008

Permalink

Nov 3rd, 2008

Re: Newton's Method - Finding Complex Roots

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

ddanbe

Reputation Points: 2035

Solved Threads: 644

Senior Poster

Online

3,738 posts
since Oct 2008

Permalink

Nov 3rd, 2008

Re: Newton's Method - Finding Complex Roots

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.

iamthwee

Featured Poster

Reputation Points: 1536

Solved Threads: 431

Posting Expert

Offline

5,865 posts
since Aug 2005

Permalink

Nov 3rd, 2008

Re: Newton's Method - Finding Complex Roots

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:

C++ Syntax (Toggle Plain Text)

typedef complex<double> Complex;

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

ArkM

Reputation Points: 1234

Solved Threads: 347

Postaholic

Offline

2,001 posts
since Jul 2008

Permalink

Nov 3rd, 2008

Re: Newton's Method - Finding Complex Roots

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

DavidB

Reputation Points: 33

Solved Threads: 9

Junior Poster

Offline

188 posts
since Jul 2006

Permalink

Nov 4th, 2008

Re: Newton's Method - Finding Complex Roots

>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

iamthwee

Featured Poster

Reputation Points: 1536

Solved Threads: 431

Posting Expert

Offline

5,865 posts
since Aug 2005

Permalink

Nov 4th, 2008

Re: Newton's Method - Finding Complex Roots

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:

Click to Expand / Collapse Quote originally posted by doll parts ...

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.

dougy83

Reputation Points: 85

Solved Threads: 45

Posting Whiz in Training

Offline

275 posts
since Jun 2007

Permalink

Nov 8th, 2008

Re: Newton's Method - Finding Complex Roots

Click to Expand / Collapse Quote 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).

DavidB

Reputation Points: 33

Solved Threads: 9

Junior Poster

Offline

188 posts
since Jul 2006

Permalink

Oct 14th, 2009

Re: Newton's Method - Finding Complex Roots

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

huss_584

Reputation Points: 10

Solved Threads: 0

Newbie Poster

Offline

7 posts
since Oct 2009

Permalink

Oct 15th, 2009

Re: Newton's Method - Finding Complex Roots

Click to Expand / Collapse Quote 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.

ithelp

Reputation Points: 769

Solved Threads: 128

Banned

Offline

1,910 posts
since May 2006

Page 1
2
Next

This thread is more than three months old

No one has posted to this discussion for at least three months. Please let old threads die and do not reply to them unless you feel you have something new and valuable to contribute that absolutely must be added to make the discussion complete. Otherwise, please start a new thread in this forum instead.

Previous Thread in C++ Forum Timeline: how can i make a movie rental store software?

Next Thread in C++ Forum Timeline: ARRAY

DaniWeb Message

Cancel Changes

User Name
Password