For this homework, we are going to consider the straightforward problem of apply
ID: 3699663 • Letter: F
Question
For this homework, we are going to consider the straightforward problem of applying Newton's method to finding the roots of the simple third-order polynomial -1. For this simple polynomial we know there are three roots, one of which by inspection is 1. The other two are complexbers whose cube is also ; the two1 v3j)/2 have this property, which you can (and should) verify in Matlab. Newton's method for finding one of these roots consists of iteratively improving an initial guess z by repeatedly applying the rule 322 until |?3-1 l is sufficiently small: we'll use 10-5 as a tolerance level for this homework. Since the roots are generally complex, so too might be z. Newton's method works perfectly well for complex values of z, but we must be sure to do the complex-valued arithmetic properly. As we saw on L2C, C++ won't do this for us natively, and we will need to implement the rules for complex subtraction, multiplication, and division manually Integer powers are just repeated multiplication, so those are implicitly covered in the rules we practiced this week). Remember that mixing real and complex arithmetic is easily accomplished by treating any real number as a complex with zero imaginary part (so 1 is really1 0j and 3 is really 3 0j in the equation above) Finally note that for the absolute value in the convergence test, you need to use the definition of the absolute value (magnitude) of a complex number Now, since we already know what the roots of this polynomial are, you might wonder why we would go through the trouble of writing a program to (at best approximately) find one. It turns out that there is a fascinating, indeed fractal, geometric figure hiding in the Newton calculations for this proble Barring pathological choices of initial guess for z (and it is possible for Newton to diverge for a very poor initial guess), any initial guess will converge to one of the three roots. The question is: which one? Theoretically, and experimentally, initial guesses in a connected region of the complex plane "surrounding" one of the three roots will converge to the nearest one. But what about regions of the plane that are approximately equidistant from two or more roots? These might converge equally well to any of the roots, and the boundaries between points which converge to different roots can be very complex (and non-obvious) resulting in a beautiful fractal structure if visualized graphically. So that's what we want to do with our program. We want it to accept as an input the choice of initial guess for z. After Newton's method has converged to a root, we want the program to "graphically" describe the root to which the initial guess has converged. For this, we'll assign a color corresponding to each of the three roots, "red" for the root at 1 "green" for the root at (-v3j)/2, and "blue" for the root at (-1 V3j)/2 A sample run of your program should look as shown at the top of the following page:
Explanation / Answer
#include<bits/stdc++.h>
#define TOLERENCE_LEVEL 0.00001
using namespace std;
// Use function to know the root value directly giving initial guess
//Example: FindRootValue(-20);
//It will output root value.
void FindRootValue(double z)
{
double h = (z*z*z - 1) / (3*z*z);
while (abs(h) >= TOLERENCE_LEVEL)
{
h = (z*z*z - 1) / (3*z*z);
z = z - h;
//cout << "Debug z : " << z<<endl;
}
cout << "Root value is : " << z;
}
//Use it when you need to guess root for given initial guess number
double newtonMethod(double z)
{
double h = (z*z*z - 1) / (3*z*z);
if (abs(h) >= TOLERENCE_LEVEL)
{
h = (z*z*z - 1) / (3*z*z);
z = z - h;
}
return z;
}
int main()
{
double initial_guess= -20;
double root = 0;
do {
cout<<"Enter number (guess): ";
cin>>initial_guess;
root = newtonMethod(initial_guess);
cout<<"initial_guess: "<<initial_guess<<" and derived root: "<<root<<endl;
} while (initial_guess != 0);
return 0;
}
Output:
Related Questions
drjack9650@gmail.com
Navigate
Integrity-first tutoring: explanations and feedback only — we do not complete graded work. Learn more.