Uwagi, zadania, przykłady ...

Macierz normalna

Macierz kwadratowa $\sf A$ jest normalna jeśli $$ \sf [A,A^\prime]=AA^\prime-A^\prime A=0, $$ gdzie $[a,b]$ jest komutatorem, a $\sf A^\prime$ oznacza macierz sprzężoną i transponowaną (Hermitowsko sprzężona). (Weisstein, Eric W. "Normal Matrix." From MathWorld--A Wolfram Web Resource. ###)

Układ normalny

Dane jest równanie macierzowe: $$ \sf Ax=b.$$ Równaniem normalnym nazywamy równanie minimalizujące sumę kwadratów różnic prawej i lewej strony: $$ \sf A^\prime Ax=A^\prime b. $$ Nazywamy je normalnym ponieważ $\sf b-Ax$ jest normalny względem zakresu $\sf A$. Tutaj $\sf A^\prime A$ jest macierzą normalną. (Weisstein, Eric W. "Normal Equation." From MathWorld--A Wolfram Web Resource. ###)

Rozkład Cholesky'ego macierzy

Zajmiemy się tylko macierzami rzeczywistymi. Rozkład Cholesky'ego polega na faktoryzacji macierzy $A$ symetrycznej i dodatnio określonej (tzn. $A'=A$ oraz $x'Ax>0$, $\forall x\in R^n$) na dwa czynniki: macierz dolną trójkątną $L$ oraz górną trójkątną $L^\prime$, gdzie $L^\prime$ jest transpozycją $L$, tak, że $A = LL^\prime$.

Ortonormalizacja metodą Cholesky'ego

Jesli $n$ liniowo niezależnych, rzeczywistych wektorów umieścimy w tablicy $V$ kolumnami, to macierz $V'V$, gdzie $V'$ oznacza macierz transponowaną, będzie macierzą symetryczną (Hermitowską) dodatnio określoną. Macierz $V'V$ można więc rozłożyć na składowe czynniki trójkątne Cholesky'ego. Mamy $V'V = LL'$, gdzie $L$ jest dolnym trójkątem rozkładu. Macierz $L$ o dodatnich elementach diagonalnych jest odwracalna. Kolumny macierzy $$ U = VL^{\prime-1} $$ są wektorami ortonormalnymi i rozpinają tę samą przestrzeń co wektory umieszczone w oryginalnej macierzy $V$. Mamy bowiem $$ U'U = (VL^{\prime-1})^\prime VL^{\prime-1} = L^{-1}V^\prime VL^{\prime-1} = L^{-1}LL^\prime L^{\prime-1} = I. $$

Zadania (18-25.XI)

  1. Przeczytać tekst z Wikipedii o ortonormalizacji zbioru wektorów metodą Grama-Schmidta i Cholesky'ego.
  2. Dokładnie zapoznać się z procedurami programu cholesky.f90
  3. Dokładnie zapoznać się z programem test_chol_ortho.f90. Wykonać kompilacjię. Uruchomić. Sprawdzić wyniki.
  4. Metodą rozkładu Choleskiego (procedury: choldc, choldcmp z programu cholesky.f90 lub test_chol_ortho.f90) zortonormalizować zbiór wektorów $\{(3,-1,-1), (-1,4,-1), (-1,-1, 5)\}$. Sprawdzić ortogonalność otrzymanych wektorów. Wykonać to samo bez komputera, stosując proces Grama-Schmidta.
  5. Napisać oddzielną procedurę cholesky_ortho.f90, która wykonuje całość obliczeń dla zadanego zbioru wektorów. Potrzebne procedury pomocnicze umieścić w module cholesky_mod.f90 (zawierającym procedury cholinv.f90, chol_ortho.f90 i inne)
  6. Napisać program wykorzystujący utworzony moduł cholesky_mod, włączając go do programu poleceniem use cholesky_mod. Sprawdzić działanie wszystkich procedur na przykładzie.
  7. Zortonormalizować układ wektorów, kolumn macierzy $$ V = \left[\begin{array}{rrrrr} 1.96 & -6.49 & -0.47 & -7.20 & -0.65 \\ -6.49 & 3.80 & -6.39 & 1.50 & -6.34 \\ -0.47 & -6.39 & 4.17 & -1.51 & 2.67 \\ -7.20 & 1.50 & -1.51 & 5.70 & 1.80 \\ -0.65 & -6.34 & 2.67 & 1.80 & -7.10 \\ \end{array}\right]$$ o ile to możliwe.
  8. Zadania wykonać w czasie zajęć w dniu 18.XI oraz w domu do 25.XI. Wyniki wydrukować.

make i makefile

Makefile opisuje działania, które wykonujemy cyklicznie w procesie kompilacji programów. Zawiera zależności między plikami i pozwala uprościć proces kompilacji. Polecenie "make" wykonane w folderze gdzie znajduje się plik 'makefile' uruchamia cały proces kompilacji opisany w 'makefile' (lub Makefile). Przykładowy 'makefile' dla kompilacji programu 'test_gs_sor' znajduje się w pliku makefile.

Równania nieliniowe

Zadania (16.xii.2015) (Hammerlin, §8)

  1. Pokazać, że ciąg $\{x_k\}$, gdzie $$ x^{(\kappa+1)} = { {x^{(\kappa)}} \over {1+(x^{(\kappa)})^2} } $$ zbiega się przy dowolnym wyborze $x^{(0)}\in R$. Wykonać 10 iteracji, startując z $x^{(0)}=1$. Przedyskutować rząd zbieżności.
  2. Załóżmy, że w celu znalezienia rozwiązania przestępnego układu równań $$ \begin{eqnarray*} x_1 = {1 \over 10}x_1^2 + \sin(x_2) \\ x_2 = \cos(x_1) + {1 \over 10} x_2^2 \end{eqnarray*} $$ w przedziale $0,7\le x_1\le0,9$; $0,7\le x_2\le0,9$ chcemy użyć metody iteracyjnej. Co można powiedzieć o zbieżności metody w związku ze stałą Lipschitza $||J_\phi||_p$ dla $p=1,\,\infty,\,F$? Znaleźć rozwiązanie z dokładnością $ \pm1\cdot10^{-5}$.

Wartości własne i wektory własne macierzy

Problem:
Dana jest macierz $A \in K^{n\times n}$, gdzie $K=R$ lub $C$. Znaleźć wartości własne i wektory własne $A$.

Dla macierzy $A(n\times n)$ wartościami własnymi są zera wielomianu charakterystycznego $p(z)=\det(zI-A)$. Zbiór zer $\lambda(A)=\{\lambda_1,\dots,\lambda_n\}$ nazywamy widmem (spektrum) macierzy. Każdej wartości własnej $\lambda\in\lambda(A)$, odpowiada wektor własny $x$, spełniający równanie $$Ax=\lambda x\,.$$ Macierz $X$ utworzona z wektorów własnych, o ile istnieje i jest nieosobliwa, pozwala przetransformować $A$ do postaci diagonalnej $$\mbox{diag}(\lambda(A))=X^{-1}AX\,.$$ Wiele metod diagonalizacji korzysta z tej tzw. transformacji podobieństwa..

Metoda potęgowa

Metoda pozwala znaleźć największą (najmniejszą) wartość własną.

Dowolny wektor $v_0$ można rozwinąć w bazie wektorów własnych $\{x_i\}$ macierzy $A$ $$ v_0 = \sum\alpha_ix_i\,. $$ Biorąc $v_m=A^mv_0=\sum\alpha_i\lambda_ix_i$, i porządkując $\lambda(A)$: $|\lambda_i|>|\lambda_{i+1}|$ for $i=1,\dots,m$, otrzymamy $$ v_m=\alpha_1\lambda_1^m\left(x_1+\sum_{i=2}^m\alpha_i \left({\lambda_i\over\lambda_1}\right)^mx_i\right)\,. $$ Dla $k\to\infty$: $$ {v_m\over\lambda_1^m} \to \alpha_1 x_1\,. $$ Mnożąc przez $y^\prime$, nieortogonalny do $v_m$, mamy $$ \lambda_1 = \lim_{m\to\infty} {{y^\prime v_{m+1}}\over y^\prime v_m} \,. $$

Algorytm

Metoda potęgowa:
$v_0\in K$ zadany wektor
for $k = 1,\dots$
     $z_k = Av_{k-1}$
     $\lambda^{(k)} = v^\prime_{k-1}z_k$
     $v_k = z_k/||z_k||$
end for

Zadania (13.01.2015)

  1. Napisać program znajdowania największej wartości własnej (ww) macierzy. Znaleźć największą ww dla macierzy $$ A=\left[\begin{array}{rrr} 2 & 1 & 0\\ 1 & 1 & 1\\ 0 & 1 & -4\\ \end{array}\right] $$ z dokładnością $10^{-6}$. Podać liczbę iteracji w funkcji dokładności w przedziale dokładności $(10^{-3}, 10^{-12})$. (Odp. -4.19852)
  2. Znaleźć najmniejszą ww macierzy z zadania poprzedniego, wykorzystując fakt, że ww macierzy odwrotnej do $A$ są odwrotnościami ww macierzy $A$. (Odp. 0.536923)
  3. Sprawdzić wyniki rachunkiem bezpośrednim. Znaleźć trzecią ww macierzy $A$. (Odp. 2.6616)
  4. Obliczyć wektory własne $x_i$ macierzy $A$. Sprawdzić że $X^{-1}AX=\mbox{diag}(\lambda(A))$, gdzie $X$ jest macierzą, której kolumnami sa $x_i$.

LAPACK

LAPACK delivers default methods for computing the entire set of eigenvalues and eigenvectors. When the matrix is unsymmetric, dgeev is used for real matrices and zgeev is used for complex matrices. For symmetric matrices, dsyevr is used for real matrices and zheevr is used for complex matrices. For generalized eigenvalues the routine dggev is used for real matrices and zggev for complex matrices. More information on LAPACK is available in the references section.

ARPACK

The Arnoldi (Lanczos) method is an iterative method used to compute a finite number of eigenvalues. The good implementation of the Arnoldi method can be found in the "ARPACK" library. The most general problem that can be solved with this technique is to compute a few selected eigenvalues for $$ Ax=\lambda Bx\,. $$ where $B\in K^{n\times n}$.

Because it is an iterative technique and only finds a few eigenvalues, it is often suitable for sparse matrices. One of the features of the technique is the ability to apply a shift $\sigma$ and solve for a given eigenvector $x$ and eigenvalue $\lambda$ (where $\sigma\neq\lambda$). $$(A-\sigma B)^{-1}Bx = xv\,,\quad\mbox{where}\quad v=1/(\lambda-\sigma)\,.$$ This is effective for finding eigenvalues near to $\sigma$.

Zwyczajne równania różniczkowe

Zadania (27.01.2016)

Metody Eulera, Heune'a

...

Metody Runge'go-Kutty

Metody wielokrokowe (Adamsa)

Last modified: śro mar 2017-03-22 14:24:13