Obliczanie pierwiastka dowolnego stopnia

Sformułowanie problemu

Zadaniem, które należy rozwiązać jest numeryczne obliczenie pierwiastka dowolnego stopnia z liczby nieujemnej:

$$\begin{array}{ccc} \displaystyle x = \sqrt[m]{a} && (a \in \m... ...{N}) \\ & \Updownarrow &\\ &\displaystyle x^m = a & \end{array}$$ (1)

Rozwiązanie

Rozwiązanie powyższego problemu przeprowadzić można za pomocą następującego schematu iteracyjnego:

$$\begin{array}{lr} x_0 = a & \\ \displaystyle x_j = \frac{1}{m... ...c{a}{(x_{j-1})^{m-1}} \right]& j = 1,2,\ldots\\ \par\end{array}$$ (2)

Wyprowadzenie

Niech

$$F(x) \equiv x^m -a$$ (3)

Poszukujemy $x^\star$ takiego, że $F(x^\star) = 0$. Dla $x^\star$ spełnione jest więc tożsamościowo:

$$({x^\star})^m - a = 0 \Rightarrow x^\star = \sqrt[m]{a}$$ (4)

Niech $x_{j-1}$ będzie przybliżoną wartością $x^\star$. wówczas w otoczeniu $x_{j-1}$ można funkcję $F(x)$ można rozwinąć w następujący szereg:

$$F(x) = F(x_{j-1}) + \frac{dF}{dx}(x_{j-1})(x-x_{j-1}) + R$$ (5)

gdzie $R$ - wyrazy wyższego rzędu. Jeżeli pominiemy człon $R$ równania (5) to wówczas zachodzi, że:

$$F(x^\star) \approx F(x_{j-1}) + \frac{dF}{dx}(x_{j-1})(x^\star - x_{j-1})$$ (6)

Pamiętając, że $F(x^\star) = 0$ otrzymujemy nowe przybliżenie dla $x_j$:

$$0 = F(x_{j-1}) + \frac{dF}{dx}(x_{j-1})(x_j - x_{j-1})$$ (7)

Drogą trywialnego przekształcenia otrzymujemy:

$$\displaystyle \frac{-F(x_{j-1})}{ \frac{dF}{dx}(x_{j-1}) } = x_j - x_{j-1}$$ (8)

$$\displaystyle x_j = x_{j-1} - \frac{-F(x_{j-1})}{ \frac{dF}{dx}(x_{j-1}) }$$ (9)

Z elementarnej analizy matematycznej wiemy, że pochodna funkcji $F(x)$ danej równaniem (3) wyraża się następująco:

$$\displaystyle \frac{dF}{dx} = m x^{m-1}$$ (10)

Podstawiając $x_{j-1}$ do równań (3), (10) i (9) otrzymujemy kolejno:

$$\displaystyle F(x_{j-1}) = (x_{j-1})^m - a$$ (11)

$$\displaystyle \frac{dF}{dx}(x_{j-1}) = m (x_{j-1})^{m-1}$$ (12)

$$\displaystyle x_j = x_{j-1} - \frac{ (x_{j-1})^m - a }{ m (x_{j-1})^{m-1} }$$ (13)

Ostatnie wyrażenie można uprościć, stosując następujące przekształcenie:

$$\begin{array}{c} \displaystyle x_{j-1} - \frac{ (x_{j-1})^m -... ...(m-1)x_{j-1} + \frac{a}{(x_{j-1})^{m-1}} \right] \\ \end{array}$$ (14)

Rozwiązanie algorytmiczne

Dla realizacji podanego powyżej schematu obliczeniowego (2) zastosować można następujący algorytm:

$x_p$ := a;
dla i:= 1 do nkrokow wykonuj
rozpocznij
	$x_p$ := ( (m - 1.0) * $x_p$ + a / (pow($x_p$, m-1) ) ) / m;
zakoncz

Przykłady

Przykład 1 Obliczanie pierwiastka kwadratowego z 4.0

Zgodnie ze schematem obliczeniowym danym równaniem (2) podstawiamy $x_0 = 4.00$ Równanie opisujące $j$-te przybliżenie rozwiązania przyjmuje postać:
$$x_j = 0.5 \left(x_{j-1} + \frac{4.00}{x_{j-1}}\right)$$
Poniżej zestawiono wyniki pierwszych 6 kroków metody.

$x_{0} =$	4.0000000000e+000	$\rightarrow$	2.5000000000e+000
$x_{1} =$	2.5000000000e+000	$\rightarrow$	2.0500000000e+000
$x_{2} =$	2.0500000000e+000	$\rightarrow$	2.0006097561e+000
$x_{3} =$	2.0006097561e+000	$\rightarrow$	2.0000000929e+000
$x_{4} =$	2.0000000929e+000	$\rightarrow$	2.0000000000e+000
$x_{5} =$	2.0000000000e+000	$\rightarrow$	2.0000000000e+000

Przykład 2 Obliczanie pierwiastka kwadratowego z 2.0

Zgodnie ze schematem obliczeniowym danym równaniem (2) podstawiamy $x_0 = 2.00$ Równanie opisujące $j$-te przybliżenie rozwiązania przyjmuje postać:
$$x_j = 0.5 \left(x_{j-1} + \frac{2.00}{x_{j-1}}\right)$$
Poniżej zestawiono wyniki pierwszych 5 kroków metody.

$x_{0} =$	2.0000000000e+000	$\rightarrow$	1.5000000000e+000
$x_{1} =$	1.5000000000e+000	$\rightarrow$	1.4166666667e+000
$x_{2} =$	1.4166666667e+000	$\rightarrow$	1.4142156863e+000
$x_{3} =$	1.4142156863e+000	$\rightarrow$	1.4142135624e+000
$x_{4} =$	1.4142135624e+000	$\rightarrow$	1.4142135624e+000

Przykład 3 Obliczanie pierwiastka stopnia 7 z 3 ( $\sqrt[7]{3}$)

Poniżej zestawiono wyniki pierwszych 11 kroków metody.

$x_{0} =$	3.0000000000e+000	$\rightarrow$	2.5720164609e+000
$x_{1} =$	2.5720164609e+000	$\rightarrow$	2.2060659436e+000
$x_{2} =$	2.2060659436e+000	$\rightarrow$	1.8946316907e+000
$x_{3} =$	1.8946316907e+000	$\rightarrow$	1.6332356394e+000
$x_{4} =$	1.6332356394e+000	$\rightarrow$	1.4224965841e+000
$x_{5} =$	1.4224965841e+000	$\rightarrow$	1.2710096113e+000
$x_{6} =$	1.2710096113e+000	$\rightarrow$	1.1910921519e+000
$x_{7} =$	1.1910921519e+000	$\rightarrow$	1.1710258809e+000
$x_{8} =$	1.1710258809e+000	$\rightarrow$	1.1699338801e+000
$x_{9} =$	1.1699338801e+000	$\rightarrow$	1.1699308128e+000
$x_{10} =$	1.1699308128e+000	$\rightarrow$	1.1699308128e+000