mirror of
https://github.com/TMD44/elte-ik-pti-bsc-zarovizsga.git
synced 2025-08-11 21:39:05 +02:00
356 lines
15 KiB
TeX
356 lines
15 KiB
TeX
\documentclass[margin=0px]{article}
|
|
|
|
\usepackage{listings}
|
|
\usepackage[utf8]{inputenc}
|
|
\usepackage{graphicx}
|
|
\usepackage{float}
|
|
\usepackage[a4paper, margin=0.7in]{geometry}
|
|
\usepackage{amsthm}
|
|
\usepackage{amssymb}
|
|
\usepackage{amsmath}
|
|
\usepackage{fancyhdr}
|
|
\usepackage{setspace}
|
|
|
|
\onehalfspacing
|
|
|
|
\newenvironment{tetel}[1]{\paragraph{#1 \\}}{}
|
|
|
|
\pagestyle{fancy}
|
|
\lhead{\it{PTI BSc Záróvizsga tételek}}
|
|
\rhead{3.1. Lineáris egyenletrendszerek iterációs módszerei}
|
|
|
|
\title{\textbf{{\Large ELTE IK - Programtervező Informatikus BSc} \vspace{0.2cm} \\ {\huge Záróvizsga tételek}} \vspace{0.3cm} \\ 3.1. Lineáris egyenletrendszerek iterációs módszerei}
|
|
\author{}
|
|
\date{}
|
|
|
|
\begin{document}
|
|
\maketitle
|
|
|
|
\subsection{Lineáris egyenletrendszerek iterációs módszerei}
|
|
|
|
A lineáris egyenletrendszert (LER) vektorsorozatokkal közelítjük, törekedve a minél gyorsabb konvergenciára.
|
|
Az iterációs módszereknek a lényege az $Ax = b \Longleftrightarrow x = Bx + c$ átalakítás. Ilyen alak létezik,
|
|
sőt nem egyértelmű, hanem sokféle lehet, és a különböző átalakítások szolgáltatják a különféle iterációs módszereket.\\
|
|
|
|
\noindent \textbf{Definíció (kontrakció)}: Az $F: \mathbb{R}^{n} \to \mathbb{R}^{n}$ függvény kontrakció, ha
|
|
$\exists 0 \leq q < 1 : \forall x,y \in \mathbb{R}^{n}:$
|
|
\begin{displaymath}
|
|
\Vert F(x) - F(y) \Vert \leq q \Vert x - y \Vert
|
|
\end{displaymath}.
|
|
|
|
\noindent A $q$ értéket kontrakciós együtthatónak nevezzük.\\
|
|
|
|
\noindent \textbf{Banach-féle fixponttétel}: Legyen $F: \mathbb{R}^{n} \to \mathbb{R}^{n}$ kontrakció a q
|
|
kontrakciós együtthatóval. Ekkor a következő állítások igazak:
|
|
|
|
\begin{enumerate}
|
|
\item $\exists! x^{*} \in \mathbb{R}^{n}: x^{*} = f(x^{*})$. Azt mondjuk, hogy $x^{*}$ az $f$ függvény
|
|
fixpontja.
|
|
|
|
\item $\forall x^{(0)} \in \mathbb{R}^{n}$ kezdőérték esetén az $x^{(k+1)} = f(x^{(k)})$ sorozat konvergens,
|
|
és $\lim \limits_{k\to\infty} x^{(k)} = x^{*}$.
|
|
|
|
\item $\Vert x^{(k)} - x^{*}\Vert \leq \frac{q^{k}}{1-q} \Vert x^{(1)} - x^{0}\Vert$.
|
|
|
|
\item $\Vert x^{(k)} - x^{*}\Vert \leq q^{k} \Vert x^{(0)} - x^{*}\Vert$.
|
|
\end{enumerate}
|
|
|
|
Vegyük észre, hogy az $Ax = b \Longleftrightarrow x = Bx + c$ átírással megteremtettük a kapcsolatot a
|
|
Banach-féle fixponttétellel, hisz most az $F(x) = Bx + c$ függvény fixpontját keressük. A fenti felírásban
|
|
$B$-t átmenetmátrixnak nevezzük.\\
|
|
|
|
\noindent \textbf{Tétel (elégséges feltétel a konvergenciára)}: Ha a LER $B$ átmenetmátrixára $\Vert B \Vert < 1$,
|
|
akkor tetszőleges $x^{(0)}$-ból indított $x^{(k+1)} := Bx^{(k)} + c$ iteráció konvergál az $Ax = b$ LER megoldásához.\\
|
|
|
|
\noindent \textbf{Tétel (Szükséges és elégséges feltétel a konvergenciára)}: Tetszőleges $x^{(0)}$-ból indított
|
|
$x^{(k+1)} := Bx^{(k)} + c$ iteráció konvergál az $Ax = b$ LER megoldásához $\Longleftrightarrow$
|
|
$\varrho(B) < 1$, ahol $\varrho(B) = \max_{1 \leq i \leq n} |\lambda_{i}(B)|$ a $B$ mátrix spektrálsugara.
|
|
|
|
\subsubsection{Jacobi-iteráció}
|
|
|
|
Tekintsük az $A \in \mathbb{R}^{n \times n}$ mátrix $L + D + U$ felbontását, ahol $L$ a mátrix szigorú alsó része, $U$ a
|
|
szigorú felső része, $D$ pedig a diagonális része. Ennek segítségével konstruáljuk meg a következő átírást:
|
|
|
|
\begin{displaymath}
|
|
Ax = b \Longleftrightarrow (L + D + U)x = b \Longleftrightarrow Dx = -(L+U)x+b \Longleftrightarrow
|
|
x = -D^{-1}(L+U)x + D^{-1}b
|
|
\end{displaymath}
|
|
|
|
\noindent A Jacobi-iteráció átmenetmátrixa tehát $B_{J} = -D^{-1}(L + U)$, maga az iteráció pedig:
|
|
|
|
\begin{displaymath}
|
|
x^{(k+1)} := -D^{-1}(L + U)x^{(k)} + D^{-1}b
|
|
\end{displaymath}
|
|
|
|
\noindent Koordinátás alakban felírva:
|
|
|
|
\begin{displaymath}
|
|
x^{(k+1)}_{i} :=
|
|
-\frac{1}{a_{ii}}
|
|
\Bigg[
|
|
\sum_{\substack{j=1\\ j \not = i}}^{n} a_{ij}x_{j}^{(k)} - b_{i}
|
|
\Bigg]
|
|
\; (i = 1, ..., n)
|
|
\end{displaymath}
|
|
|
|
\noindent \textbf{Tétel}: Ha az A mátrix szigorúan diagonálisan domináns a soraira, akkor
|
|
$\Vert B_{J} \Vert_{\infty} < 1$ (azaz konvergens a módszer).\\
|
|
|
|
\noindent \textbf{Tétel}: Ha az A mátrix szigorúan diagonálisan domináns az oszlopaira, akkor
|
|
$\Vert B_{J} \Vert_{1} < 1$ (azaz konvergens a módszer).
|
|
|
|
\subsubsection{Csillapított Jacobi-iteráció}
|
|
|
|
Továbbra is a Jacobi-iterációval foglalkozunk, csak egy plusz $\omega$ paraméter bevezetésével próbáljuk
|
|
finomítani a módszert. Tekintsük a $Dx = -(L + U)x + b$ egyenletet, valamint a triviális $Dx =
|
|
Dx$ egyenletet. Ezeket rendre szorozzuk meg $\omega$, illetve $1 - \omega$ értékekkel, majd adjuk össze a két
|
|
egyenletet:
|
|
|
|
\begin{displaymath}
|
|
Dx = (1 - \omega)Dx -\omega(L+U)x + \omega b
|
|
\end{displaymath}
|
|
|
|
\noindent Szorozzunk $D^{-1}$-zel:
|
|
|
|
\begin{displaymath}
|
|
x = (1 - \omega)Ix -\omega D^{-1}(L+U)x + \omega D^{-1}b \Longleftrightarrow
|
|
x = ((1 - \omega)I -\omega D^{-1}(L+U))x + \omega D^{-1}b
|
|
\end{displaymath}
|
|
|
|
\noindent Ez alapján $B_{J(\omega)} = (1 - \omega)I -\omega D^{-1}(L+U)$ és $c_{J}(\omega) = \omega D^{-1}b$.\\
|
|
|
|
\noindent Észrevehető, hogy $\omega = 1$ esetén pont a Jacobi-iterációt kapjuk vissza.\\
|
|
|
|
\noindent Koordinátás alakban felírva:
|
|
|
|
\begin{displaymath}
|
|
x^{(k+1)}_{i} =
|
|
(1 - \omega)x^{(k)}_{i}
|
|
-\frac{\omega}{a_{ii}}
|
|
\Bigg[
|
|
\sum_{\substack{j=1\\ j \not = i}}^{n} a_{ij}x_{j}^{(k)} - b_{i}
|
|
\Bigg]
|
|
\; (i = 1, ..., n)
|
|
\end{displaymath}
|
|
|
|
\noindent \textbf{Tétel}: Ha $J(1)$ konvergens, akkor $\omega \in (0,1)$-re $J(\omega)$ is az.
|
|
|
|
\subsubsection{Gauss-Seidel iteráció}
|
|
|
|
\noindent Egy másik lehetséges iteráció konstruálásának az ötlete a következő:
|
|
|
|
\begin{displaymath}
|
|
Ax = b \Longleftrightarrow (L + D + U)x = b \Longleftrightarrow (L+D)x = -Ux+b \Longleftrightarrow
|
|
x = -(L+D)^{-1}Ux + (L+D)^{-1}b
|
|
\end{displaymath}
|
|
|
|
\noindent Ez az ötlet szüli a Gauss-Seidel iterációt, vagyis:
|
|
|
|
\begin{displaymath}
|
|
x^{(k+1)} := -(L+D)^{-1}Ux^{(k)} + (L+D)^{-1}b
|
|
\end{displaymath}
|
|
|
|
Az iteráció átmenetmátrixa tehát $B_{S} = -(L+D)^{-1}U$. A koordinátás alak felírásához kicsit átírjuk
|
|
az iterációt:
|
|
|
|
\begin{displaymath}
|
|
(L+D)x^{(k+1)} = -Ux^{(k)} + b
|
|
\end{displaymath}
|
|
|
|
\begin{displaymath}
|
|
Dx^{(k+1)} = -Lx^{(k+1)} - Ux^{(k)} + b
|
|
\end{displaymath}
|
|
|
|
\begin{displaymath}
|
|
x^{(k+1)} = -D^{-1} \big[Lx^{(k+1)} + Ux^{(k)} - b \big]
|
|
\end{displaymath}
|
|
|
|
\begin{displaymath}
|
|
x^{(k+1)}_{i} =
|
|
-\frac{1}{a_{ii}}
|
|
\Bigg[
|
|
\sum_{j=1}^{i-1} a_{ij}x_{j}^{(k+1)} +
|
|
\sum_{j=i+1}^{n} a_{ij}x_{j}^{(k)} -
|
|
b_{i}
|
|
\Bigg]
|
|
\; (i = 1, ..., n)
|
|
\end{displaymath}
|
|
|
|
\noindent \textbf{Megjegyzés}: Az implementáció során elég egyetlen $x$ vektort eltárolni, és annak a komponenseit sorban felülírni, ugyanis
|
|
láthatjuk, hogy az első $i-1$ komponenst már az "új", $x^{(k+1)}$ vektorból vesszük.\\
|
|
|
|
\noindent \textbf{Tétel}: Ha $A$ szigorúan diagonálisan domináns
|
|
\begin{enumerate}
|
|
\item a soraira, akkor
|
|
$\Vert B_{S} \Vert_{\infty} \leq \Vert B_{J} \Vert_{\infty} < 1$.
|
|
|
|
\item az oszlopaira, akkor
|
|
$\Vert B_{S} \Vert_{1} \leq \Vert B_{J} \Vert_{1} < 1$.
|
|
\end{enumerate}
|
|
|
|
\noindent Azaz a Gauss-Seidel is konvergens, és legalább olyan gyors, mint a Jacobi.
|
|
|
|
\subsubsection{Relaxációs módszer}
|
|
|
|
A relaxációs módszer lényegében a csillapított Gauss-Seidel iterációt jelenti. Ennek megkonstruálásához
|
|
tekintsük az $(L+D)x = -Ux + b$ és $Dx = Dx$ egyenleteket. Ezeket rendre szorozzuk meg $\omega$, illetve
|
|
$1 - \omega$ értékekkel, majd adjuk össze a két egyenletet:
|
|
|
|
\begin{displaymath}
|
|
(D+\omega L)x = (1 - \omega)Dx -\omega Ux + \omega b
|
|
\end{displaymath}
|
|
|
|
\begin{displaymath}
|
|
x = (D+\omega L)^{-1}\big[(1 - \omega)D -\omega U \big]x + \omega (D+\omega L)^{-1}b
|
|
\end{displaymath}
|
|
|
|
Az iteráció tehát: $x^{(k+1)} = (D+\omega L)^{-1}\big[(1 - \omega)D -\omega U \big]x^{(k)} + \omega (D+\omega L)^{-1}b$, ahol
|
|
az átmenetmátrix: $B_{S(\omega)}= (D+\omega L)^{-1}\big[(1 - \omega)D -\omega U \big]$. A koordinátás alak
|
|
felírásához itt is átírjuk kicsit az iterációt:
|
|
|
|
\begin{displaymath}
|
|
(D + \omega L)x^{(k+1)} = (1 - \omega)Dx^{(k)} -\omega Ux^{(k)} + \omega b
|
|
\end{displaymath}
|
|
|
|
\begin{displaymath}
|
|
Dx^{(k+1)} = -\omega Lx^{(k+1)} -\omega Ux^{(k)} + \omega b + (1 - \omega)Dx^{(k)}
|
|
\end{displaymath}
|
|
|
|
\begin{displaymath}
|
|
x^{(k+1)} = -\omega D^{-1} \big[Lx^{(k+1)} + Ux^{(k)} - b \big] + (1 - \omega)x^{(k)}
|
|
\end{displaymath}
|
|
|
|
\begin{displaymath}
|
|
x^{(k+1)}_{i} =
|
|
-\frac{\omega}{a_{ii}}
|
|
\Bigg[
|
|
\sum_{j=1}^{i-1} a_{ij}x_{j}^{(k+1)} +
|
|
\sum_{j=i+1}^{n} a_{ij}x_{j}^{(k)} -
|
|
b_{i}
|
|
\Bigg] +
|
|
(1 - \omega) x_{i}^{(k)}
|
|
\; (i = 1, ..., n)
|
|
\end{displaymath}
|
|
|
|
\noindent Vegyük észre, hogy $\omega = 1$ esetén a Gauss-Seidel iterációt kapjuk.\\
|
|
|
|
\noindent \textbf{Tétel}: Ha a relaxációs módszer konvergens minden kezdővektorból indítva, akkor $\omega \in (0,2)$.\\
|
|
|
|
\noindent \textbf{Megjegyzés}: Ha $\omega \notin (0,2)$, akkor általában nem konvergens a módszer (bár adott feladat esetén előfordulhat,
|
|
hogy találunk olyan kezdővektort, amelyből indítva konvergál a módszer).\\
|
|
|
|
\noindent \textbf{Tétel}: Ha $A$ szimmetrikus és pozitív definit és $\omega \in (0, 2)$, akkor a relaxációs módszer konvergens. Ennek
|
|
következménye a Gauss-Seidel iteráció konvergenciája ($\omega = 1$ eset).\\
|
|
|
|
\noindent \textbf{Tétel}: Ha $A$ tridiagonális, akkor $\varrho(B_{S}) = \varrho(B_{J})^{2}$, azaz a Jacobi és Gauss-Seidel iteráció
|
|
egyszerre konvergens, illetve divergens.\\
|
|
|
|
\noindent \textbf{Tétel}: Ha $A$ szimmetrikus, pozitív definit és tridiagonális, akkor a $J(1)$, $S(1)$ és $S(\omega)$ $\omega \in (0, 2)$-
|
|
re konvergens, és $S(\omega)$-ra az optimális paraméter értéke:
|
|
|
|
\begin{displaymath}
|
|
\omega_{0} = \frac{2}{1 + \sqrt{1 - \varrho(B_{J})^{2}}}
|
|
\end{displaymath}
|
|
|
|
\subsubsection{Richardson-iteráció}
|
|
|
|
Legyen $p \in \mathbb{R}$. Így
|
|
|
|
\begin{displaymath}
|
|
Ax = b \Longleftrightarrow
|
|
0 = -Ax + b \Longleftrightarrow
|
|
0 = -pAx + pb \Longleftrightarrow
|
|
x = (I-pA)x +pb
|
|
\end{displaymath}
|
|
|
|
Az iteráció tehát $x^{(k+1)} := (I-pA)x^{(k)} +pb$. Az átmenetmátrix: $B_{R(p)} = I-pA)$. Az
|
|
$r^{(k)} := b - Ax^{(k)} $ vektort maradékvektornak (reziduumvektornak) nevezzük, hiszen
|
|
|
|
\begin{displaymath}
|
|
x^{(k+1)} = x^{(k)} - pAx^{(k)} + pb = x^{(k)} + pr^{(k)}
|
|
\end{displaymath}
|
|
|
|
\begin{displaymath}
|
|
r^{(k+1)} = b - Ax^{(k+1)} = b - A(x^{(k)} + pr^{(k)}) = r^{(k)} - pAr^{(k)}
|
|
\end{displaymath}
|
|
|
|
\noindent Tekintsük az előállítás algoritmusát: $r^{(0)} := b - Ax^{(0)}$, továbbá a fentiek miatt:
|
|
|
|
\begin{displaymath}
|
|
x^{(k+1)} := x^{(k)} + pr^{(k)}
|
|
\end{displaymath}
|
|
|
|
\begin{displaymath}
|
|
r^{(k+1)} := r^{(k)} - pAr^{(k)}
|
|
\end{displaymath}
|
|
|
|
\noindent \textbf{Tétel}: Ha $A$ szimmetrikus, pozitív definit, a sajátértékei pedig a következők:
|
|
\begin{displaymath}
|
|
0 < m := \lambda_{1} \leq \lambda_{2} \leq ... \leq \lambda_{n} =: M
|
|
\end{displaymath}
|
|
|
|
\noindent akkor $p \in (0,\frac{2}{M})$ esetén $R(p)$ konvergens, és az optimális paraméter: $p_{0} = \frac{2}{m + M}$.
|
|
Továbbá igaz, hogy: $\varrho(B_{R(p_{0})}) = \frac{M - m}{M + m}$.
|
|
|
|
\subsection{Spline-interpoláció}
|
|
|
|
Az eddig említett interpolációs módszerekben polinomokkal dolgoztunk. Lehetőség van arra is, hogy a megadott pontrendszerre más
|
|
típusú függvényt próbáljunk illeszteni. Igen előnyös tulajdonságokkal rendelkeznek a bizonyos folytonossági előírásoknak is
|
|
megfelelő, szakaszonként polinom függvények, a spline-ok.\\
|
|
|
|
\noindent \textbf{$l$-edfokú spline}: Legyen adott $\Omega_{n} = \left\{x_{0}, x_{1}, ..., x_{n}\right\}$ az $[a,b]$ intervallum egy
|
|
felosztása, ahol $x_{0}=a, x_{n}=b$ és $l \in \mathbb{N}$. Az $s:[a,b] \to \mathbb{R}$ függvény egy $l$-edfokú spline az
|
|
$\Omega_{n}$-re vonatkozóan, ha:
|
|
|
|
\begin{enumerate}
|
|
\item $s_{|[x_{k-1},x_{k}]}$ egy $l$-edfokú polinom $\forall k = 1,..,n$
|
|
|
|
\item $s \in C^{l-1}[a,b]$, tehát a teljes intervallumon $(l-1)$-szer folytonosan derviálható
|
|
\end{enumerate}
|
|
|
|
\noindent Jelölés: $s_{l}(\Omega_{n})$ az $\Omega_{n}$-hez tartozó $l$-edfokú spline-ok halmaza.\\
|
|
|
|
\noindent \textbf{Spline-interpoláció}: Legyenek adottak $x_{k},f(x_{k})$ értékek $k=0,1,..,n$-re és $l \in \mathbb{N}$.
|
|
Keressük azt az $s \in s_{l}(\Omega_{n})$ spline-t, amelyre $s(x_{k}) = f(x_{k})$. Ehhez elő kell állítanunk minden
|
|
intervallumra egy $l$-edfokú polinomot. Ha a polinomokat az együtthatóikkal reprezentáljuk, akkor ez $n(l+1)$ ismeretlen.
|
|
Az előírt feltételek száma: $2n$ interpolációs és $(l-1)(n-1)$ folytonossági feltétel, hiszen csak a belső pontokban kell
|
|
előírni az illető deriváltakra vonatkozó megfelelő folytonossági feltételt. Az így kapott összes feltétel darabszáma
|
|
$(l+1)n - (l-1)$, tehát az egyértelműséghez $l-1$ feltétel hiányzik még. Ezeket úgynevezett peremfeltételekkel adjuk meg.
|
|
Pl. a harmadfokú spline-interpolációhoz 2 peremfeltétel szükséges. Ezek a következők (ezek közül elég egyet választani,
|
|
mert mindegyik 2 feltételt tartalmaz):
|
|
|
|
\begin{enumerate}
|
|
\item Természetes peremfeltétel: $s''(a) = s''(b) = 0$.
|
|
|
|
\item Hermite-féle peremfeltétel: $s'(a) = s_{a}, s'(b) = s_{b}$, ahol $s_{a}, s_{b}$ előre megadott számok.
|
|
|
|
\item Periodikus peremfeltétel (ekkor feltételezzük, hogy $s(a) = s(b)$ is teljesül):
|
|
$s'(a) = s'(b)$ és $s''(a) = s''(b)$
|
|
\end{enumerate}
|
|
|
|
\noindent \textbf{Elsőfokú spline előállítása}: Az elsőfokú spline előállítása triviális szakaszonkénti
|
|
lineáris Lagrange-interpolációval.\\
|
|
|
|
\noindent \textbf{Másodfokú spline előállítása}: Egyetlen peremfeltétel szükséges, legyen a következő: $s'(a) = s_{a}$
|
|
valamilyen $s_{a}$ számra. Az $[x_{0},x_{1}]$ szakaszon Hermite-interpolációval előállítjuk azt a $H_{2}$ másodfokú
|
|
polinomot, amely megfelel az interpolációs feltételeknek és a peremfeltételnek. Az így kapott polinom $x_{1}$-beli
|
|
deriváltja meghatározott, tehát a folytonos deriválhatóság miatt az $[x_{1},x_{2}]$ szakaszon a bal végpontban
|
|
adott a derivált értéke. Ismét Hermite-interpolációt alkalmazva megkapjuk az $[x_{1},x_{2}]$ szakaszhoz tartozó
|
|
polinomot. Ezt az eljárást ismételve állíthatjuk elő a másodfokú interpolációs spline-t.\\
|
|
|
|
\noindent \textbf{Függvény tartója}: A $supp(f) := \overline{\left\{x \in \mathbb{R}: f(x) \not = 0 \right\}}$ halmazt
|
|
az $f$ függvény tartójának nevezzük.\\
|
|
|
|
\noindent \textbf{Számegyenes felosztása}: $\Omega_{\infty} := \left\{...,x_{-2},x_{-1},x_{0},x_{1},...x_{n},x_{n+1},...\right\}$\\
|
|
|
|
\noindent \textbf{B-spline}: A $B_{l,k}, k \in \mathbb{Z}$ $l$-edfokú spline függvények rendszerét B-spline függvényeknek
|
|
nevezzük, ha az alábbi feltételek teljesülnek:
|
|
\begin{enumerate}
|
|
\item $supp(B_{l,k}) = [x_{k},x_{k+l+1}]$, azaz a tartója minimális
|
|
|
|
\item $B_{l,k}(x) \geq 0$
|
|
|
|
\item $\displaystyle\sum_{k \in \mathbb{Z}}B_{l,k}(x) = 1$
|
|
\end{enumerate}
|
|
|
|
\end{document} |