Hello again ! Hello @jules
For the exercise one and general information about my talk at ADC 17, see there :
Exercise 2
Now for the exercise two, I’ll make you play with the Newton’s Raphson algorithm all by yourself !
I’ll starting by explaining again (and better) the example provided previously for Newton-Raphson’s algorithm with the numeric calculus for the equation x*x - 5 = 0. As I said during my talk, the purpose of that algorithm is to calculate the “roots” of a given equation g(x), which means the value(s) for x so g(x) = 0. It is quite useful for the so-called “implicit equations”, which means equations for which there is no explicit solution that can be written output = “something depending only of inputs”.
But that can be used as well to calculate numeric approximations of some explicit equations / functions, as alternate ways to get the output of given std functions without the need to call them. It’s like reverse-engineering the inside of some well known std functions behaviour !
So if g(x) = x*x - 5, then the roots are very probably sqrt(5) and -sqrt(5). But thanks to that algorithm, you will be able to get a numeric value for sqrt(5) without any call to any C++ sqrt function. This is an iterative algorithm, which must be initialized with a given value x0, and called several times in succession to get the x_k, improving the accuracy of the result at each iteration, using this formula :
$x_{k+1} = x_k - (dg(x_k)/dx)^-1 * g(x_k)$
dg(x)/dx is the derivative function of g(x) depending on x, and the ^-1 means that we are basically going to compute Newton-Raphson’s algorithm when everything is one dimensional by computing g(x_k) divided by the value of (dg(x_k)/dx), otherwise we need to invert a square matrix of the right dimension.
So in our first example case, here is the expression for all these functions :
- g(x) = x * x - 5
- dg(x)/dx = 2 * x (if don’t understand why, then you need to take some math lessons about derivatives of classic functions I’m afraid !)
So let’s initialize the algorithm with x0 = 1. Using the algorithm formula, we can calculate the next iteration x1 :
x1 = x0 - g (x0) / (dg(x0)/dx) = 1 - (1 * 1 - 5) / (2 * 1) = 3.
If we do the same thing several times we get :
- x2 = 2.333333333333334
- x3 = 2.230895238095238
- x4 = 2.236068895643363
- x5 = 2.236067977499978
- x6 = 2.236067977499790
etc.
Tell me if you have any question so far And the code for doing it in JUCE is in the zip archive provided in the first topic.