II. RF KMF DokuWiki

8.1 Fixpont iterációs eljárás (Fokozatos közelítések módszere)
8.2 Newton-módszer (Newton-Kantorovics módszer)
8.3 Gradiens-módszer (Lejtő-módszer)

Legyen

$$x = f (x)\tag{8.1}\label{eq:8.1}$$

ahol

$$f : \mathbb{R}^n \rightarrow \mathbb{R}^n \tag{8.2}\label{eq:8.2}$$

folytonos.

Tegyük fel, hogy

$$ f(x)\in D,\quad D\subset\mathbb{R}^n,\quad x\in D,\tag{8.3}\label{eq:8.3}$$

$D$ – zárt tartomány, és

$$||f(x)-f(y)||\leqslant q || f(x)-f(y) ||,\quad 0\leqslant q<1 \tag{8.4}\label{eq:8.4}$$

Akkor tetszőleges $x_{0}\in D$ esetén a

$$x_{k+1} = f(x_k)\tag{8.5}\label{eq:8.5}$$

iterációs folyamat konvergens.

A kilépési feltételek lehetnek:

$$|| f(x_k) || \leqslant ε \tag{8.6}\label{eq:8.6}$$

vagy

$$||x_{k+1} -x_k|| \leqslant ε_2\tag{8.7}\label{eq:8.7}$$

Két egyenlet két változóval ($n=2$). $$\begin{cases} F_1(x, y) =0 \\ F_2(x, y) =0 \end{cases}\tag{8.8}\label{eq:8.8}$$

A $\eqref{eq:8.8}$ (8.8) egyenletrendszert átalakíthatjuk: $$\begin{cases} x = φ_1(x, y)\\ y = φ_2(x, y) \end{cases} \tag{8.9}\label{eq:8.9}$$ (8.9)

ahol

$$φ_1(x, y),\quad φ_2(x, y)$$

iteráló függvények.

Az iterációs algoritmus: $$\begin{cases} x_{n+1} = φ_1(x_n, y_n)\\ y_{n+1} = φ_2(x_n, y_n) \end{cases}\!,\quad n =0, 1, 2, … \tag{8.10}\label{eq:8.10}$$ (8.10)

ahol az $(x_0, y_0)$ a kezdő iteráció (pont)

8.1. Tétel

Legyen az $\mathbb{R}(a \leqslant x\leqslant A, b\leqslant y \leqslant B)$ -ben

$$ \begin{cases} x = φ_1(x, y)\\ y = φ_2(x, y), \end{cases}$$

egyenletrendszernek egy és csak egy megoldása: ($x = x^*, y =y^*$).

Ha 1) a

$$φ_1(x, y), \quad φ_2(x, y),$$

függvények az $\mathbb{R}$-ben differenciálhatók,

2) $(x_n, y_n)\in\mathbb{R}\quad n =0, 1, 2, …$

3) és az $\mathbb{R}$-ben teljesülnek a

$$\begin{equation}\begin{aligned}\begin{cases} \left|\displaystyle\frac{\partial\varphi_1}{\partial x}\right| + \left|\displaystyle\frac{\partial\varphi_2}{\partial x}\right| \leqslant q_1 <1 \\[5pt] \left|\displaystyle\frac{\partial\varphi_1}{\partial y}\right| + \left|\displaystyle\frac{\partial\varphi_2}{\partial y}\right| \leqslant q_2 <1 \end{cases}\end{aligned}\end{equation} \tag{8.11}\label{eq:8.11}$$ $$$$ feltételek,

akkor az iterációs folyamat

$$\begin{cases} x_{n+1} =φ_1 (x_n, y_n)\\ y_{n+1} =φ_2 (x_n, y_n)\\ \end{cases},\quad n = 0, 1, 2, …\tag{8.12}\label{eq:8.12}$$

konvergens:

$$\begin{equation}\begin{aligned} \lim_{n\to\infty}x_n&=x^*,\\ \lim_{n\to\infty}y_n&=y^*. \end{aligned}\end{equation}\tag{8.13}\label{eq:8.13}$$ Ez a tétel akkor is teljesül, ha a 3) feltétel helyet a következőt alkalmazzuk: $$\begin{equation}\begin{aligned}\begin{cases} \left|\displaystyle\frac{\partial\varphi_1}{\partial x}\right| + \left|\displaystyle\frac{\partial\varphi_1}{\partial y}\right| \leqslant q_1 <1 \\[5pt] \left|\displaystyle\frac{\partial\varphi_2}{\partial x}\right| + \left|\displaystyle\frac{\partial\varphi_2}{\partial y}\right| \leqslant q_2 <1 \end{cases}\end{aligned}\end{equation} \tag{8.14}\label{eq:8.14}$$ (8.14) A hiba-becslés: $$|x_n-x^*|+|y_n-y^*|\leqslant M \frac{|x_n-x_{n-1}|+|y_n-y_{n-1}|}{1-M}$$ (8.15) $$M =\max(q_1, q_2 )$$ A gyakorlati szempontból elegendő, ha $M<\displaystyle\frac{1}{2}$.

$$$$

8.1. Példa

$$\begin{cases} x^3 + y^3 - 6x + 3 &= 0\\ x^3 - y^3 - 6y + 2 &= 0 \end{cases}$$

A megoldást három biztos számjeggyel akarjuk kapni.

$$\begin{cases} x = φ_1(x, y) = \displaystyle\frac{x^3 + y^3}{6} +\displaystyle\frac{1}{2}\\ y = φ_2(x, y) = \displaystyle\frac{x^3 - y^3}{6} +\displaystyle\frac{1}{3} \end{cases}$$

Legyen

$$R = \{0 \leqslant x \leqslant 1, 0 \leqslant y \leqslant 1\}$$

Ha $(x_0, y_0)\in R$ akkor

$$\begin{cases} 0 \leqslant φ_1(x_0, y_0) \leqslant 1,\\ 0 \leqslant φ_2(x_0, y_0) \leqslant 1, \end{cases}$$

Mivel

$$0 \leqslant \frac{x_0^3 + y_0^3}{6} \leqslant \frac{1}{6}$$

$$-\frac{1}{6} \leqslant \frac{x_0^3 - y_0^3}{6} \leqslant \frac{1}{6}$$

akkor a $(x_n, y_n)$ pontok is az $R$-ben maradnak, úgy hogy

$$\frac{1}{2} \leqslant x \leqslant \frac{5}{6}$$

$$\frac{1}{6} \leqslant x \leqslant \frac{1}{2}$$

Akkor

$$\left|\displaystyle\frac{\partial\varphi_1}{\partial x}\right| + \left|\displaystyle\frac{\partial\varphi_1}{\partial y}\right| = \frac{x^2}{2} + \frac{y^2}{2} < \frac{\displaystyle\frac{25}{36} +\displaystyle\frac{1}{4}}{2} =\frac{34}{72} <1 $$

$$\left|\displaystyle\frac{\partial\varphi_2}{\partial x}\right| + \left|\displaystyle\frac{\partial\varphi_2}{\partial y}\right| = \frac{x^2}{2} + \frac{y^2}{2} < \frac{\displaystyle\frac{25}{36} +\displaystyle\frac{1}{4}}{2} =\frac{34}{72} <1 $$

Legyen

$$x_0 = \frac{1}{2};\quad y_0 = \frac{1}{2};$$

Akkor

$$x_1 = \frac{1}{2} + \frac{\displaystyle\frac{1}{8}+\displaystyle\frac{1}{8}}{6} = 0,\!542,$$

$$y_1 = \frac{1}{3} + \frac{\displaystyle\frac{1}{8} -\displaystyle\frac{1}{8}}{6} = 0,\!333,$$

$$x_2 = \frac{1}{2} + \frac{0,\!1915}{6} = 0,\!533,$$

$$y_2 = \frac{1}{3} + \frac{0,\!1223}{6} = 0,\!354,$$

$$x_3 = 0,\!533,\quad y_3 = 0,\!351,$$

$$x_4 = 0,\!532,\quad y_4 = 0,\!351,$$

A megoldás:

$$(x^*, y^*) = (0,\!532, 0,\!351)$$

A Fixpont iterációs eljárás alkalmazását egy egyenlet esetén lásd a 6.9 Fejezetben.

Javasoljuk megoldani a 10. Fejezetben található feladatokat.

$$f(x)=0,\quad x\in\mathbb{R}^n\tag{8.16}\label{eq:8.16}$$

vagy $$\begin{cases} f_1(x_1, x_2, … , x_n) =0\\[7pt] f_2(x_1, x_2, … , x_n) =0\\[7pt] ...................... \\[7pt] f_n(x_1, x_2, … , x_n) =0 \end{cases}\tag{8.17}\label{eq:8.17}$$

A $f_k(x)$ függvényeket linearizáljuk az $x^{(i)}= (x_1^{(i)}, x_2^{(i)}, …, x_n^{(i))}$ pontban:

$$\begin{equation}\begin{aligned} &f_k(x_1, x_2, … ,x_n) ≈ f_k(x_1^{(i)},x_2^{(i)}, …,x_n^{(i)}) + \\ &+\sum_{j=1}^n\frac{\partial}{\partial x_j}f_k(x_1^{(i)}, x_2^{(i)}, …, x_n^{(i)})(x_j-x_j^{(i)}),\quad k=1,2,\ldots, n \end{aligned}\end{equation} \tag{8.18}\label{eq:8.18}$$ vagy vektor formában: $$\begin{equation}\begin{aligned} &f_1(x)\approx f_1(x^{(i)})+\nabla f_1(x^{(i)})^{T}(x-x^{(i)}) \\ &\cdots\cdots\cdots \\ &f_n(x)\approx f_n(x^{(i)})+\nabla f_n(x^{(i)})^{T}(x-x^{(i)}) \\ \end{aligned}\end{equation} \tag{8.19}\label{eq:8.19}$$ Akkor az $f(x) =0$ egyenletrendszer megoldását a linearizált egyenletrendszer

$$\begin{equation}\begin{aligned} &f_1(x^{(i)})+\nabla f_1(x^{(i)})^{T}(x-x^{(i)}) = 0 \\ &\cdots\cdots\cdots \\ &f_n(x^{(i)})+\nabla f_n(x^{(i)})^{T}(x-x^{(i)}) = 0 \\ \end{aligned}\end{equation} \tag{8.20}\label{eq:8.20}$$ megoldása alapján keressük. Közelítő megoldásként a $x^{(i+1)}$ vektort tekintjük. Ha a Jacobi-mátrix-ot alkalmazunk:

$$ J(x)=\left[\frac{\partial f_i(x)}{\partial x_j}\right]_{i,j=1}^n= \begin{pmatrix} \displaystyle\frac{\partial f_1}{\partial x_1} & \displaystyle\frac{\partial f_2}{\partial x_2} & \cdots & \displaystyle\frac{\partial f_1}{\partial x_n} \\[6pt] \displaystyle\frac{\partial f_2}{\partial x_1} & \displaystyle\frac{\partial f_2}{\partial x_2} & \cdots & \displaystyle\frac{\partial f_2}{\partial x_n} \\[6pt] \cdots & \cdots &\cdots &\cdots \\[6pt] \displaystyle\frac{\partial f_n}{\partial x_1} & \displaystyle\frac{\partial f_n}{\partial x_2} & \cdots & \displaystyle\frac{\partial f_n}{\partial x_n} \\[6pt] \end{pmatrix}=\begin{bmatrix}\nabla f_1(x)^T\\ \cdots \\ \nabla f_n(x)^T\end{bmatrix} \tag{8.21}\label{eq:8.21}$$

akkor a

$$f(x^{(i)}) +J(x^{(i)} ) (x - x^{(i)}) =0 \tag{8.22}\label{eq:8.22}$$

egyenletrendszer megoldása így állapítható meg:

$$x^{(i+1)} = x^{(i)}- \left[J(x^{(i)} )\right]^{-1} f(x^{(i)}), \quad i =0, 1, 2, …\tag{8.23}\label{eq:8.23}$$

8.2. Példa $$\begin{equation}\begin{aligned} x^2 +y^2 + z^2 &= 1 \\ 2x^2 +y^2 - 4 z &= 0 \\ 3x^2 - 4y^2 +z^2 &= 0 \end{aligned}\end{equation}$$ $$(x_0, y_0, z_0) = (0,\!5; 0,\!5; 0,\!5)$$ $$$$

$$f(x)=\begin{pmatrix} x^2 +y^2 + z^2 -1 \\ 2x^2 +y^2 - 4 z \\ 3x^2 - 4y^2 +z^2 \end{pmatrix}$$

$$f(x^{(0)})=\begin{pmatrix} 0,\!25 +0,\!25 + 0,\!25 -1 \\ 0,\!25 +0,\!25 - 2,\!00\\ 0,\!75 - 2,\!00 +0,\!25 \end{pmatrix}= \begin{pmatrix} -0,\!25 \\ -1,\!25 \\ -1,\!00 \end{pmatrix} $$

$$J(x)=\begin{pmatrix} 2x & 2y & 2y \\ 4x & 2y & -4 \\ 6x & -4 & 27 \end{pmatrix}$$

$$J(x^{(0)})=\begin{pmatrix} 1 & 1 & 1 \\ 2 & 1 & -4 \\ 3 & -4 & 1 \end{pmatrix}$$

$$\det(J(x^{(0)})=|J(x^{(0)})|=\begin{vmatrix} 1 & 1 & 1 \\ 2 & 1 & -4 \\ 3 & -4 & 1 \end{vmatrix} = -40 $$

$$\left[J(x^{(0)})\right]^{-1}=-\frac{1}{40} \begin{pmatrix} -15 & -5 & -5 \\ -14 & -2 & 6 \\ -11 & 7 & -1 \end{pmatrix}= \begin{pmatrix} \displaystyle\frac{3}{8} & \displaystyle\frac{1}{8} & \displaystyle\frac{1}{8} \\ \displaystyle\frac{7}{20} & \displaystyle\frac{1}{20} & -\displaystyle\frac{3}{20} \\ -\displaystyle\frac{11}{40} & -\displaystyle\frac{7}{40} & \displaystyle\frac{1}{40} \end{pmatrix}$$

$$x^{(1)} = x^{(0)}- \left[J(x^{(0)} )\right]^{-1} f(x^{(0)})=$$

$$=\begin{pmatrix} 0,\!5 \\ 0,\!5 \\ 0,\!5 \end{pmatrix}- \begin{pmatrix} \displaystyle\frac{3}{8} & \displaystyle\frac{1}{8} & \displaystyle\frac{1}{8} \\ \displaystyle\frac{7}{20} & \displaystyle\frac{1}{20} & -\displaystyle\frac{3}{20} \\ -\displaystyle\frac{11}{40} & -\displaystyle\frac{7}{40} & \displaystyle\frac{1}{40} \end{pmatrix} \cdot \begin{pmatrix} -0,\!25 \\ -1,\!25 \\ -1,\!00 \end{pmatrix} = \begin{pmatrix} 0,\!875 \\ 0,\!500 \\ 0,\!375 \end{pmatrix}. $$

Az $x^{(2)}$ számítása:

$$f(x^{(1)})=\begin{pmatrix} 0,\!875^2 +0,\!500^2 + 0,\!375^2 -1 \\ 2\cdot 0,\!875^2 +0,\!500^2 - 4\cdot 0,\!275\\ 3\cdot 0,\!875^2 - 4\cdot 0,\!005 +0,\!375^2 \end{pmatrix}= \begin{pmatrix} 0,\!15625 \\ 0,\!28125 \\ 0,\!43750 \end{pmatrix} $$

$$J(x^{(1)})=\begin{pmatrix} 1,\!750 & 1 & 0,\!750 \\ 3,\!500 & 1 & -4 \\ 5,\!250 & -4 & 0,\!750 \end{pmatrix}$$

$$\det(J(x^{(1)})=|J(x^{(1)})|=\begin{vmatrix} 1,\!750 & 1 & 0,\!750 \\ 3,\!500 & 1 & -4 \\ 5,\!250 & -4 & 0,\!750 \end{vmatrix} = -64,\!75 $$

$$\left[J(x^{(1)})\right]^{-1}=-\frac{1}{64,\!75} \begin{pmatrix} -15,\!52 & -3,\!75 & -4,\!75 \\ -23,\!625 & -2,\!6250 & 9,\!625 \\ -19,\!25 & 12,\!25 & -1,\!75 \end{pmatrix}$$

$$x^{(2)} = x^{(1)}- \left[J(x^{(1)} )\right]^{-1} f(x^{(1)})=$$

$$=\begin{pmatrix} 0,\!875 \\ 0,\!500 \\ 0,\!375 \end{pmatrix}+ \frac{1}{64,\!75} \begin{pmatrix} -15,\!52 & -3,\!75 & -4,\!75 \\ -23,\!625 & -2,\!6250 & 9,\!625 \\ -19,\!25 & 12,\!25 & -1,\!75 \end{pmatrix}\cdot \begin{pmatrix} 0,\!15625 \\ 0,\!28125 \\ 0,\!43750 \end{pmatrix}= \begin{pmatrix} 0,\!78981 \\ 0,\!49662 \\ 0,\!36993 \end{pmatrix}. $$

Hasonló módon kapjuk meg az

$$x^{(3)} = \begin{pmatrix} 0,\!78981 \\ 0,\!49662 \\ 0,\!36993 \end{pmatrix}\quad f(x^{(3)}) = \begin{pmatrix} 0,\!0001 \\ 0,\!00004 \\ 0,\!00005 \end{pmatrix}. $$

A megoldás:

$$(x^*, y^*, z^*) = (0,\!7852; 0,\!4966; 0,\!3699) $$

Ezt a feladatot a Jacobi-mátrix invertálása nélkül is meg lehet oldani, mivel a $\eqref{eq:8.23}$ (8.23) egyenletrendszert így átalakíthatjuk:

$$J(x^{(i)} )(x^{(i+1)} - x^{(i)} ) = f(x^{(i)} ),\quad i = 0, 1, 2, … \tag{8.24}\label{eq:8.24}$$

vagy

$$J(x^{(i)})Δx_i = f(x^{(i)} ),\quad i = 0, 1, 2, … \tag{8.25}\label{eq:8.25}$$

ahol

$$Δx_i = x^{(i+1)} - x^{(i)}\tag{8.26}\label{eq:8.26}$$

Akkor az ismeretlen $x$ vektort a $\eqref{eq:8.24}$ (8.24) lineáris egyenletrendszer megoldásának az alkalmazásával lehet közelíteni, és a következő iterációs folyamatot kapunk:

1) $x^{(0)}$ kiválasztása,

2) $J(x^{(i)})Δx_i = f(x^{(i)})$ egyenletrendszer megoldása, ahol az ismeretlen a $Δx_i$,

3) $x^{(i+1)} = x^{(i)}+ Δx_i,\ i =0, 1, 2,$ és a következő iteráció végrehajtása (a második lépés megismétlése).

Az iterációkat addig folytatjuk, amíg a

$$||Δx_i|| < ε$$ (8.27)

feltétel nem teljesül.

8.3. Példa

$$\begin{cases} F(x, y) =0 \\[4pt] G(x, y) =0 \end{cases}$$

$$|J(x,y)|= \begin{vmatrix} \displaystyle\frac{\partial}{\partial x}F(x,y) & \displaystyle\frac{\partial}{\partial y}F(x,y) \\[6pt] \displaystyle\frac{\partial}{\partial x}G(x,y) & \displaystyle\frac{\partial}{\partial y}G(x,y) \\[6pt] \end{vmatrix} \neq 0 $$

$$|J_1(x,y)|= \begin{vmatrix} F(x,y) & \displaystyle\frac{\partial}{\partial y}F(x,y) \\[6pt] G(x,y) & \displaystyle\frac{\partial}{\partial y}G(x,y) \\[6pt] \end{vmatrix},$$

$$|J_2(x,y)|= \begin{vmatrix} \displaystyle\frac{\partial}{\partial x}F(x,y) & F(x,y) \\[6pt] \displaystyle\frac{\partial}{\partial x}G(x,y) & G(x,y) \\[6pt] \end{vmatrix},$$

$$x_{k+1} = x_k -\frac{|J_1(x_k, y_k)|}{|J(x_k, y_k)|}$$

$$y_{k+1} = y_k -\frac{|J_2(x_k, y_k)|}{|J(x_k, y_k)|}$$

$$\begin{cases} F(x, y) = 2x^3 - y^2 - 1 = 0\\[4pt] G(x, y) = xy^3 - y - 4 = 0 \end{cases}$$

$$|J(x,y)|= \begin{vmatrix} 6x^2 & 2y \\ y^3 & 3xy^2-1 \\ \end{vmatrix}$$

$$(x_0 , y_0) = (1,\!2; 1,\!7)$$

$$|J(1,\!2; 1,\!7)| = 97,\!910$$

$$x_1 = x_0 -\frac{|J_1(x_0, y_0)|}{|J(x_0, y_0)|}=1,\!2- \frac{1}{97,\!910} \begin{vmatrix} -0,\!434 & -3,\!40 \\ 0,\!1956 & 9,\!4 \end{vmatrix}=1,\!2349$$

$$y_1 = y_0 -\frac{|J_2(x_0, y_0)|}{|J(x_0, y_0)|}=1,\!7- \frac{1}{97,\!910} \begin{vmatrix} 8,\!64 & -0,\!434 \\ 4,\!91 & 0,\!1956 \end{vmatrix}=1,\!6610$$

$$(x_1 , y_1) = (1,\!2349; 1,\!6610)$$

$$(x_2 , y_2) = (1,\!2343; 1,\!6615)$$

A Newton-módszer alkalmazását egy egyenlet esetén lásd a 6.6 Fejezetben.

Javasoljuk megoldani a 10. Fejezetben található feladatokat.

Legyen

$$\begin{cases} f_1(x_1, x_2, … , x_n) =0\\[6pt] f_2(x_1, x_2, … , x_n) =0\\[6pt] .................... \\[6pt] f_n(x_1, x_2, … , x_n) =0\\[6pt] \end{cases}\tag{8.28}\label{eq:8.28}$$

nemlineáris egyenletrendszer.

A $\eqref{eq:8.28}$ alapján szerkesztünk

$$\Phi(x_1, x_2, … ,x_n)=\sum_{i=1}^nf_i^2(x_1, x_2, … ,x_n)\geqslant 0 \tag{8.29}\label{eq:8.29}$$

függvényt, amely a minimális értékét a $\eqref{eq:8.28}$ megoldásán éri el:

$$\min \Phi(x_1, x_2, … ,x_n)\tag{8.30}\label{eq:8.30}$$

Ez azt jelenti, hogy ha megoldjuk a $\eqref{eq:8.30}$ feladatot, akkor egyidejűleg megoldottuk a $\eqref{eq:8.28}$ egyenletrendszert is. A $\eqref{eq:8.30}$ optimum-problémát több módszerrel is lehet megoldani. Alkalmazzuk a lejtő-módszert.

Kiszámítjuk a függvény gradiensét:

$$\nabla \Phi(x) = \begin{bmatrix} \displaystyle\frac{\partial \Phi(x)}{\partial x_1}, \displaystyle\frac{\partial \Phi(x)}{\partial x_2}, \ldots, \displaystyle\frac{\partial \Phi(x)}{\partial x_n} \end{bmatrix} \tag{8.31}\label{eq:8.31}$$

és kiválasztjuk a megoldás kezdő közelítését (iterációját) $x_0$. A következő iterációkat a

$$x_{m+1} := x_{m} - \alpha_m \nabla\Phi(x_m) \tag{8.32}\label{eq:8.32}$$

képlet alapján kapjuk,

ahol az $\alpha_m$ a

$$\Theta_m(\alpha) = \Phi\left(x_m - \alpha_m \nabla \Phi(x_m)\right) \tag{8.33}\label{eq:8.33}$$

függvény minimuma.

Javasoljuk megoldani a 10. Fejezetben található feladatokat.