===== 8. Nemlineáris egyenletrendszerek ===== 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)\\ ==== 8.1 Fixpont iterációs eljárás (Fokozatos közelítések módszere) ==== 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. ==== 8.2. Newton-módszer (Newton-Kantorovics módszer) ==== $$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. ==== 8.3. Gradiens-módszer (Lejtő-módszer) ==== 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.