Newton’s Iteration
Summary
Newton’s method is a powerful method to find the root of an analytic function. It’s condition is that you must be able to calculate the derivative of f(x) at every point. Newton’s method converges quickly for starting values near the root but becomes chaotic as you start further away from the root. This article demonstrates how you can quickly compute the Newton’s method iterations using C++ in ImageTank and how to change the input and functions interactively to explore convergence.
Setting up the program
Start by creating a table output since the C++ program will return a result table. In the Task menu, click on the “Returns a Table” action.
Then fill in the settings shown in the photo below. Make sure that for the N variable you have the ‘Integer’ check box checked. If you don’t do that the value will be defined as a double and the code that you paste it will not compile. You need to hand in the initial value, how many iterations to take and the functions for both f and its derivative. The function will be passed is as an analytical function which the C++ library (DTSource) handles. This streamlines trying different functions without having to alter code or recompiling. Note also that I also specify the structure of the returned table (lower right corner). That way ImageTank knows the structure without having to run your program.
Next create the Xcode project, for details of how to set up the project folder see the following link. https://community.visualdatatools.com/imagetank/knowledge-base/simple-group/
Paste in the following code:
The C++ Program
DTTable Computation(int N,double x0,const DTFunction1D &f,
const DTFunction1D &fp)
{
DTMutableDoubleArray xn(N);
DTMutableDoubleArray fxn(N);
DTMutableDoubleArray fpxn(N);
DTMutableDoubleArray step(N);
double increment;
double x = x0;
double fv,fpv;
for (int i=0;i<N;i++) {
xn(i) = x;
fxn(i) = fv = f(x);
fpxn(i) = fpv = fp(x);
step(i) = increment = -fv/fpv;
x += increment;
}
DTMutableList<DTTableColumn> columns(4);
columns(0) = CreateTableColumn("xn",xn);
columns(1) = CreateTableColumn("fxn",fxn);
columns(2) = CreateTableColumn("fpxn",fpxn);
columns(3) = CreateTableColumn("step",step);
DTTable toReturn(columns);
toReturn.pinfo(); // For debug purposes
return toReturn;
}
The previous example did not use DTSource so I will spend the next section explaining what it is and how it is used in the code above. DTSource is an object library used in ImageTank. These objects are designed to tie back into the graphical interface portion of ImageTank. It is designed to reduce the amount of coding done on your part and while much of it is not strictly necessary it is very useful.
If you want details on what the different objects and functions do details can be found in the header files in Xcode. You can do this by holding down the command key and clicking on a given class name such as DTFunction1D or DTMutableList.
- DTFunction1D – This is a class that overwrites the () operator so that f(3) evaluates the function at 3. What DTFunction1D stores is a tree structure that describes the function. This is not a compiled function, so it is a lot slower than if you had a function defined.
- DTMutableDoubleArray xn(N) – This is an object that contains a list of numbers. This calls the constructor that allocates memory for N double precision numbers. You can read more about this in the DTDoubleArray.h file, but what this does it to create an array that is indexed using (), so xn(0) is the first index, xn(1) the second etc. If you access entries outside of the range you will get a run-time error. The “Mutable” part means that you can modify values. There is a DTDoubleArray as well, but for that you can only access values but not change them.
- DTMutableList<DTTableColumn> – The DTList and DTMutableList are templates to create a list of objects, in this case of type DTTableColumn. Just like for the DTMutableDoubleArray, you have both read and write access to those entries, and any access out of bounds will print an error message but not halt the program.
- DTTableColumn – This is a single column. It can have multiple types. Each column has a name and you first have to create a list of colums before you can create a table.
- columns(0) = CreateTableColumn(“xn”,xn) – The function takes in two values, the name of the column and the content of the column. Note that this function is heavily overloaded, which means that the column that is created depends on the argument list and what type the arguments are. Since the second argument is a list of double precision numbers the column that is created is a number column. If it was a DTStringList data type you would create a text column, but what is returned is always a DTTableColumn. See DTTable.h for more information.
- DTTable toReturn(columns) – This creates the table from the columns.
- toReturn.pinfo() – This is a debugging aid, it just displays a short description of the structure of the table. You can also print the entire table by using toReturn.pall(), but clearly ImageTank will be easier to view the table.
Viewing the result in ImageTank
Now let’s see the output of the C++ code in ImageTank. Note that the Xcode project is called “Newton iteration”, below that is the Debug tab. When you click on the Test button it will run the program using the current input and show you the text output of the program. Next to the structure definition there is a small monitor button, and if you press that you will see the content of the output.
Below the Debug entry in the side panel is the “Execution Log” entry. This shows you the output for every time that ImageTank ran the program to compute the output. It shows up three times since I hit the reload button in the Program tab. Otherwise ImageTank will only run the program if one of the inputs change and store the results. If you recompile your program you need to hit the Reload button so that ImageTank clears the cached results.
Looking at the result
Once this is working, you can view the result. You can see the result in the variable monitor for the table, but in this case the values quickly converge to the root, square root of 2. Since the C++ program did not try to figure out what the iteration converged to, let’s compute the error in ImageTank. The first step is to go into the Gear menu and select “Map Columns”.
This sets up another table. You need to set up columns and how they should be computed. By default you have one numerical column. In this one I used the expression “xn-sqrt(2)” The xn refers to the name of the column in the input table. Note that table for the Xcode program has been called “Computed” and in the “Map Table” table you see that name in the Source menu. You can change the name of the variables at any time, the connection is made to the object but not the name or location of the variable. If the column name changes from xn the “error” expression in the mapped table will have to change as well. The first entry in the mapped table just copies a column from the original table, create that entry by using the “Add column” menu above the list.
If you now change the input, everything is automatically re-computed. For example if you change the initial guess
If you change the function, the same thing happens. Note that here the function x^2+2 has no root, and you can see how Newton’s method bounces around
The variable monitor for a table has a few different visualization methods. One is a x-y plot, where you can pick the columns for x and y.
Here I take 100 iterations and it bounces around seemingly randomly.