** HP Prime: Approximate of a Quartic Root**

**Introduction**

In the article "Square Root & Cube Root Algorithms" (see source below), teacher and educator Dave Elgin wrote an article on how his Advanced Higher Applied Mathematics class developed algorithms to estimate the square root and cubic roots of numbers. The algorithms are first based off of Netwon's Method, then uses selected initial guesses and solving for linear systems.

**Elgin's Derivation **

**Square Root**

Suppose x^2 = k. To set up for Newton's Method, let f(x) = x^2 - k, with df/dx = 2x. Then

x_n+1 = x_n - (x_n^2 - k) / (2 * x_n) = 1/2 * (x_n + k / x_n^2)

(The article uses N for the number to find the root of, but to eliminate confusion, I use k. Completely a choice of labels.)

The class used a pattern to determine guesses for the square root of k:

k / (x_n), (k^2) / (x_n^3), (k^3) / (x_n^5), and so on.

Let g(x) be an iterative function where x_n+1 = g(x_n) and for a second-order approximation:

g(x) = a1 * x + a2 * k / x + a3 * k^2 / x^3

Two derivatives of g(x) are taken:

g'(x) = a1 - a2 * k / x^2 - 3 * a3 * k^2 / x^4, with g'(x_n) = 0

g''(x) = 2 * a2 * k / x^3 + 12 * a3 * k^2 / x^5 with g''(x_n) = 0

This requires the following system of equations to be solved for a1, a2, and a3 (after substituting x = √k):

1 = a1 + a2 + a3

0 = a1 - a2 - 3 * a3

0 = 2 * a2 + 12 * a3

leading to the solutions a1 = 3/8, a2 = 3/4, and a3 = -1/8

Hence the second-order recursive function for the square root is (after simplifying):

g(x) = 3/8 * x + (3 * k) / (4 * x) - k^2 / (8 * x^3)

which translates to

x_n+1 = 3/8 * x_n + (3 * k) / (4 * x_n) - k^2 / (8 * x_n^3)

**Cube Root**

They repeat the same process for the cubic root, which I will briefly outline here:

x^3 = k, f(x) = x^3 - k, f'(x) = 3x^2

x_n+1 = x_n - (x^3 - k) / (3x^2) = 1/3 * (2 * x_n - k / (x_n^2))

With guess of k / (x_n^2) and k^2 / (x_n^5) used, the iterative function is set up as:

g(x) = a1 * x + a2 * k / x^2 + a3 * k^2 / x^5

and

g'(x) = a1 - 2 * a2 * k / x^3 - 5 * a3 * k^2 / x^6

g''(x) = 6 * a2 * k / x^4 + 30 * a3 * k^2 / x^7

and with g(x_n) = x_n+1, g'(x_n) = 0, g''(x_n) = 0 and substituting x = k^1/3, the system becomes:

1 = a1 + a2 + a3

0 = a1 - 2 * a2 - 5 * a3

0 = 6 * a2 + 30 * a3

with the solutions a1 = 5/9, a2 = 5/9, and a3 = -1/9, giving the second-order recursive function:

g(x) = 5/9 * x + (5 * k) / (9 * x^2) - k^2 / (9 * x^5)

The article shows the derivation of a third-order recursive function for both square and cube root.

**Deriving a Second-Order Algorithm for Quartic Roots**

Let's use a similar approach used in Elgin's article to develop an algorithm to calculate the fourth (quartic) root:

k^1/4 = x

Let f(x) = x^4 - k, then f'(x) = 4*x^3, and

x_n+1 = x_n - (x_n^4 - k) / (4 * x_n^3) = 3/4 * x_n - k / (4 * x_n^3)

Use guesses x_n, k / (x_n^3), k^2 / (x_n^7), we set up the equations:

g(x) = a1 * x + a2 * k / x^3 + a3 * k^2 / x^7

g'(x) = a1 - 3 * a2 * k / x^4 - 7 * a3 * k^2 / x^8

g''(x) = 12 * a2 * k / x^5 + 56 * a3 * k^2 / x^9

Setting g(x) = x^1/4, g'(x) = 0, g''(x) = 0, and setting g(k^1/4), we get the system:

1 = a1 + a2 + a3

0 = a1 - 3 * a2 - 7 * a3

0 = 12 * a2 + 56 * a3

The solutions to above system: a1 = 21/32, a2 = 7/16, a3 = -3/32, which gives the second order recursive equation:

g(x) = 21/32 * x + (7 * k) / (32 * x^3) - (3 * k) / (32 * x^7)

The program FTHROOT use the recursive equation to approximate the quartic root.

**HP Prime Program: FTHROOT**

EXPORT FTHROOT(k)

BEGIN

// EWS 2020-10-21

// Approx 4th Root

LOCAL r,r0,r1,ri;

r:=k^0.25;

r0:=0;

r1:=√k;

ri:=0;

WHILE ABS(r0-r1)>1á´‡−10 DO

ri:=ri+1;

r0:=r1;

r1:=(21*r0)/32+(7*k)/(16*r0^3)-(3*k^2)/(32*r0^7);

END;

PRINT();

PRINT("4√"+PRINT(k));

PRINT("Root = "+STRING(r));

PRINT("------");

PRINT("Approximation: "+

STRING(r1));

PRINT("Iterations: "+STRING(ri));

END;

The choice of a good first guess is necessary with any iterative root finding process. The program FTHROOT chooses the square root of k for an initial guess. The goal is to seek a positive root.

**Examples**

Each example is followed by a set of screen shots, which include setting up Sequences and their graphs on the HP Prime.

**Example 1**

k = 176.4

Result: 3.64438831256 (algorithm took 7 iterations with initial guess √176.4)

Example 2

k = 5525

Result: 8.62150472576 (algorithm took 9 iterations with initial guess √5525)

Source

Eddie

All original content copyright, © 2011-2020. Edward Shore. Unauthorized use and/or unauthorized distribution for commercial purposes without express and written permission from the author is strictly prohibited. This blog entry may be distributed for noncommercial purposes, provided that full credit is given to the author.