Metody numeryczne, dr inż. Magdalena A
apińska
Wprowadzenie do metod numerycznych
Podstawowe pojęcia:
błąd bezwględny=| wartość przybliżona-wartość dokładna |,
|wartość przybliżona-wartość dokładna|
błąd wględny= ,
|wartość dokładna|
algorytm niestabilny,
zdarzenie z
le uwarunkowne.
Wprowadzenie pojęcia interpolacji.
Interpolacja Lagrange a:
F (x) = a0 + a1x + a2x2 + · · · + anxn
Wielomian Lagrange a:
n
(x - x0)(x - x1) . . . (x - xi-1)(x - xi+1) . . . (x - xn)
Ln(x) = yi ,
(xi - x0)(xi - x1) . . . (xi - xn)
i=0
możemy to również zapisać jako
n
yi
Ln(x) = wn ,
(x - xi)(xi - x0)(xi - x1) . . . (xi - xn)
i=0
gdzie
wn = (x - x0)(x - x1) . . . (x - xn).
BÅ‚Ä…d interpolacji Lagrange a:
Mn+1
|f(x) - Ln(x)| d" |wn(x)| ,
(n + 1)!
gdzie Mn+1 = supad"xd"b |f(n+1)(x)|.
Zadanie 1
Znalez
ć wielomian interpolacyjny, który w punktach -2,1,2,4 przyjmuje wartości 3,1,-3,8.
1
Metody numeryczne, dr inż. Magdalena A
apińska
Zadanie 2
Korzystając ze wzoru interpolacyjnego Lagrange a napisać własną funkcję, która dla wezłów
podanych przez użytkownika i ich wartości tworzy wielomian interpolacyjny Lagrange a.
Zadanie 3
Ocenić z jaką dokładnością można obliczyć wartość ln 100.5 przy użyciu wzoru interpola-
cyjnego Lagrange a, jeżeli dane są wartości ln 100, ln 101, ln 102, ln 103.
Zadanie 4
Znalez
ć wielomian interpolacyjny, który w punktach 0,2,3,5,6 przyjmuje wartości 1,3,2,5,6.
Zadanie 5
"
"
Obliczyć wartość 117 za pomocą wzoru interpolacyjnego dla funkcji y = x i wezłów inter-
polacji 100,121,144. Oszacować błąd.
Zadanie 6
Zapoznaj się z działaniem funkcji InterpolatingPolynomial.
InterpolatingP olynomial[{{x1, y1}, . . . , {xn, yn}}, x]
2
Metody numeryczne, dr inż. Magdalena A
apińska
Interpolacja 28.02.2011
Zadanie 1
Z jaka dokładnoscia mozna oszacowac wartosc sin(1.885) majac dane sin(0) = 0, sin(0.6283) =
0.5878, sin(2.3562) = 0.7071.
Wielomiany Czebyszewa pierwszego rodzaju
T0(x) = 1
T1(x) = x
Tk(x) = 2x Tk-1(x) - Tk-2(x), k = 2, 3, . . .
Wielomiany Czebyszewa pierwszgeo rodzaju są określone na przedziale [-1; 1]. Jeśli inter-
polujemy funkcjÄ™ f(t), gdzie a d" t d" b,
a + b b - a
t = + x.
2 2
a d" t d" b wtedy i tylko wtedy gdy -1 d" x d" 1
Zera wielomianu Czebyszewa
2i + 1
xi = cos Ä„, (i = 0, 1, . . . , n)
2n + 1
Zadanie 2
Napisać własną funkcję, która wypisuje i rysuje n wielomianów Czebyszewsa.
Zadanie 3
Znajdz
wielomiany Czebyszewa na przedziale [1, 4].
Zadanie 4
O godzinie 12 temperatura wynosiła 24 stopnie, o 13-25,14-23,15-20, a o 16-16. Oblicz tem-
peraturÄ™ o godzinie 14.30. Skorzystaj z interpolacji Czebyszewa.
Ilorazy róznicowe
RzÄ…d pierwszy:
f(x1) - f(x0)
f(x0, x1) =
x1 - x0
f(x2) - f(x1)
f(x1, x2) =
x2 - x1
1
Metody numeryczne, dr inż. Magdalena A
apińska
RzÄ…d drugi:
f(x1, x2) - f(x0, x1)
f(x0, x1, x2) =
x2 - x0
f(xn-1, xn) - f(xn-2, xn-1)
f(xn-2, xn-1, xn) =
xn - xn-2
Zadanie 5
Utworzyć tablicę ilorazów różnicowych dla f(x) = x3 o węzłach interpolacji 0, 2, 3, 5, 6.
Zadanie 6
Napisać własną funkcję służacą do obliczania ilorazów różnicowych funkcji f(x),gdzie węzły
oraz odpowiadające im wartości podane są przez użytkownika.
Wzór interpolacyjny Newtona
Przyjmijmy oznaczenia analogiczne do przedstawionych wcześniej,
wn(x) = (x - x0)(x - x1) . . . (x - xn),
Wn(x) = f(x0) + f(x0, x1)w0(x) + f(x0, x1, x2)w1(x) + · · · + f(x0, . . . , xn)wn-1(x).
Zadanie 7
Napisać wzór interpolacyjny dla funkckji f(x) określinej tablicą wartości f(0) = 1, f(2) =
3, f(3) = 2, f(4) = 5, f(6) = 7.
Wykonać samodzielnie:
Zadanie 8
Sformułować pojęcia interpolacji Newtona dla węzłów równoległych.
Zadanie 9
Korzystając ze wszytskich omówionych interpolacji znalez
ć wielomiany interpolacyjne dla
węzłów i ich wartości (1, 1), (1.5, 3), (2, 4), (2.5, 0), (2, 3).
2
Metody numeryczne, dr inż. Magdalena A
apińska
Równania nieliniowe
Zadanie 1
Znalez
ć pierwiatski równania
ln(x + 2) - 2x2 + 1 = 0.
(wykorzystaj Mathematice).
Metoda połowienia przedziału
Zadanie 2
Znalez
ć metodą połowienia pierwiastek
f(x) = x3 + x2 - 3x - 3,
w przedziale < 1, 2 >.
Zadanie 3
Napisz własną funkcję, która dla podanego przedziału oraz funkcji, znajduje jej miejsca zerowe
korzystając z metody połowienie przedziałów.
f[x] = x3 + x2 - 3x - 3;
przybliz[1, 2, f]
Otrzymany wynik porównaj z Mathematica.
Pytanie: Jakie są wady i zalety metody połowienia przedziałów?
Metoda stycznych
Zadanie 4
Stosując metodę Newtona obliczyć dodatni pierwiastej równania
f(x) = x3 + x2 - 3x - 3,
w przedziale < 1, 2 >.
Zadanie 5
Napisać program realizujący metodę stycznych.
Pytanie: Jakie sÄ… wady i zalety metody Newtona?
Metoda siecznych
1
Metody numeryczne, dr inż. Magdalena A
apińska
Zadanie 6
Znalez
ć miejsca zerowe funkcji
y = 3x + sin x - ex
w przedziale < 0, 1 > za pomocÄ… metody siecznych.
Zadanie 7
Napisać program realizujący metodę siecznych.
Pytanie: Jakie sÄ… wady i zalety metody siecznych?
Zadanie 8
StosujÄ…c metodÄ™ Newtona znalez
ć pierwiastki równania x3 - 2x + 1 = 0.
Zadanie 9
Znalez
ć dodatnie pierwiastki równania ex - 3x2 = 0 metodą Newtona.
Zadanie 10
Jaka jest różnica pomiędzy metodą połowienia przedziału, a metodą siecznych.
Zadanie 11
Mając zaprogramowane trzy wyżej omówione metody porównać ich czas obliczeń dla tego
samego problemu.
Zadanie 12
Znalez
ć z dokladnoscią = 0.1 pierwiastek równania f(x) = tan3 x-4 tan x = 0 w przedziale
[-0.5, 0.2] metodą połowienia przedziału.
Zadanie 13
Znalez
ć z dokladnoscią = 0.1 pierwiastek równania f(x) = ex-1 + x2 - 2 = 0 w przedziale
[0, 2] metodÄ… siecznych.
Zadanie 14
2
Znalez
ć z dokladnoscią = 0.001 pierwiastek równania f(x) = 2x -5x+10 - 64 = 0 w
przedziale [0, 1.25] metodÄ… stycznych.
Zadanie 15
Porównać metody: połowienia pzredziału, siecznych , stycznych przy obliczeniu pierwiatsków
równania f(x) = -10x -5x4 -20 = 0 w zadanym przedziale [0.3, 3.1] z dokładnością = 0.1.
2
Metody numeryczne, dr inż. Magdalena A
apińska
Równania nieliniowe i układy równań nieliniowych
Zadanie 1
Obliczyć metodą iteracji prostej ujemny pierwiastek funkcji z dokładnością
ln(x + 2) - 2x2 + 1 = 0.
= 10-5.
Wskazówka: [-0.8, -0.7].
Zadanie 2
Napisać własną funkcję zwracającą wartość Jakobianu dla danego układu równań.
Przetestuj na funkcji f[x_] := {ArcT an[x] - y3, 4 " x2 + 9 " y2 - 36}.
Zadanie3
x2 - 2x + y = 1
Wykonać jedną iterację metodą Newtona dla ,
x + xy - 2y = -8
gdzie X0 = [4 - 6]T .
Zadanie 4
Napisać własną funkcję realizującą metodę Newtona dla układu równań podanego przez użytkown-
ika.
StyczneN[f_, a_, e_, N_]
Przetestować dla przykładu z poprzedniego zadania.
Zadanie 5
Å„Å‚
x2 2
òÅ‚ - x2 - 2 = 0
1
Wyprowadzić wzór Newtona dla ,
ół
x1 - x2 = 0.
Zadanie 6
Który z nastepujących wielomianów pierwszego stopnia a.(6-2x)/17, b.(3-x)/8,c.-(x+4)/4
jest wielomianem interpolacyjnym dla f(x) = 1/(3 + x).Odpowiedz
uzasadnić. Wsk: Naszki-
cować wykres.
Zadanie 7
Wiedząc, że x = {2, 3, -6}. Oblicz x , x , x .
1 2 3
Zadanie 8
îÅ‚ Å‚Å‚
1 2 3
ðÅ‚ ûÅ‚.
A = 4 5 6 Oblicz A , A .
1 2
7 8 9
1
Metody numeryczne, dr inż. Magdalena A
apińska
Liczba pierwiastków w zadanym przedziale 21.03.2011
Dla zadanego wielomianu budujemy ciÄ…g Sturma
f0(x) = f(x),
f1(x) = f (x),
f2(x) = reszta z dzielenia f0(x) przez f1(x)wzięta ze znakiem przeciwnym,
f3(x) = reszta z dzielenia f1(x) przez f2(x)wzięta ze znakiem przeciwnym.
Jeżeli ciąg f(xi(x)), i = 0, 1, . . . jest ciągiem Sturma na przedziale (a, b) i f0(a)f0(b) jest
różne od 0 to liczba różnych zer rzeczywistych wielomianu f0(x) leżących w przedziale jest
równa N(a) - N(b).
Zadanie 1
Zastosować twierdzenie Sturma do określenia liczby pierwiastków rzeczywistych wielomianu
f(x) = x3 + x2 - x - 1.
Zadanie 2
Ile kroków należy wykonać metodą bisekcji, aby rozwiązać równanie
x3 - 7x2 + 14x - 6 = 0,
gdy [a, b] = [0, 2].
Zadanie 3
Wykonać jedną iterację metodą siecznych dla równania x4 - x3 - 7x2 + x + 8 = 0 dla x0 = 1
i x1 = 2.
Zadanie 4
Co się stanie jeśli zastosujemy metodę Newtona dla równania x3 - 5x, x0 = 1.
Zadanie 5
Znalez
ć rozwiązanie równania x2 - 1 = 0 w przedziale [a, b] = [-1.3, -0.5] metodą bisekscji
zakładając wielkość błędu = 0.25.
Zadanie 6
Napisać własną funkcję, która dla danego równania postacji axn + bxn-1 + . . . znajduje jej
miejsca zerowe korzystajÄ…c z metodty prostych iteracji.
Zadanie 7
Napisać własną funkcję, która dla macierzy podanej przez użytkownika wyznacza jej wyz-
nacznik korzystając z Algorytmu Chio (założenie a11 = 0).

1
Metody numeryczne
Zadania do wykonania na 28 kwietnia
Zadanie 1
Zapoznaj się z algorytmami rozwiązywania układów równań liniowych przedstawionymi na
wykładzie:
" Eliminacja Gaussa
" Rozkład Lu
" Rozkład Cholesky ego .
Zadanie 2
Napisać własną funkcję rozwiązującą układ równań podany przez u\
ytkownika metodÄ…
Gaussa.
Zadanie 3
Napisać własną funkcję, która dla podanej macierzy A tworzy macierz L i macierz U.
Metody numeryczne, dr inż. Magdalena A
apińska
Układy równań liniowych 28.04.2011
Zadanie 1
Sprwadzić czy podana macierz jest dodatnio określona
2 1
A = .
1 2
Zadanie 2
Sprawdzić czy podana macierz jest diagonalnie dominująca
ëÅ‚ öÅ‚
4 -1 0 -1
ìÅ‚ ÷Å‚
-1 4 0 -1
ìÅ‚ ÷Å‚
A = .
íÅ‚ Å‚Å‚
-1 0 4 -1
0 -1 -1 4
Zadanie 3
Stosując metodę Gaussa rozwiąż układ równań
îÅ‚ Å‚Å‚ îÅ‚ Å‚Å‚
9 3 4 x1 7
ðÅ‚ ûÅ‚ ðÅ‚
4 3 4 x2 ûÅ‚ = 8 .
1 1 1 x3 3
Zadanie 4
Stosując metodę Gaussa rozwiąż układ równań
Å„Å‚
2x
ôÅ‚ - 3y - z + 2w + 3v = 4
ôÅ‚
òÅ‚
4x - 4y - z + 4w + 11v = 4
.
2x
ôÅ‚ - 5y - 2z + 2w - v = 9
ôÅ‚
ół
2y + z + 4v = -5
Zadanie 5
Stosując metodę Gaussa rozwiąż układ równań
x - y = 4
.
2x - 2y = -4
Zadanie 6
Kiedy układ będzie miał nieskończenie wiele rozwiązań?
Rozkład Doolittle a:
A = LU do rozwiÄ…zania AX = b.
Postępowanie:
1
Metody numeryczne, dr inż. Magdalena A
apińska
 LY = b
 UX = Y
i-1
uij = aij - likukj,
k=1
i-1
aji - ljkuki
k=1
lji = ,
uii
Zadanie 7
Przedstaw rozkład macierzy dla rozkładu Crouta.
Zadanie 8
Rozłóż korzystając z rozkładu LU,
ëÅ‚ öÅ‚
3 3 0
íÅ‚ Å‚Å‚
A = 0 2 2
1 0 1
Zadanie 9
Znalez
ć rozkład LU dla
1 3
A = ,
2 2
wykorzystaj rozwiązując układ Ax = [3, 4]T .
Rozkład Choleskiego:
A = LLT do rozwiÄ…zania AX = b.
Postępowanie:
 LY = b
 LT X = Y
i-1
lii = aii - ljklik2, i = 1, 2, . . . , n,
k=1
i-1
lji = aji - ljklik, j = i + 1, i + 2, . . . , n.
k=1
Zadanie 9
Znalez
ć rozkład Choleskiego dla
4 -1
A = ,
-1 41
4
2
Metody numeryczne, dr inż. Magdalena A
apińska
Zadanie 10
Opracuj algorytm odwracania macierzy kwadratowej korzystając z rozkładu LU.
ëÅ‚ öÅ‚
3 3 0
íÅ‚ Å‚Å‚
A = 0 2 2
1 0 1
Zadanie 11
Jeśli macierz A jest rzeczywista, symetryczna, dodatnio określona, to ma ona jednoznaczny
rozkład na czynniki postacji A = LLT ,L-dolnotrójkątna o dodatnich elmentach na przekątnej.
Udowodnij ( patrz wykład oraz literatura).
Uwaga: Na laboratoria 5 maja zapoznaj się z metodami iteracyjnymi rozwiązywania układów
równań przedstawionymi na wykładzie
3
Metody numeryczne, dr inż. Magdalena A
apińska
Metody iteracyjne dkla układów równań liniowych
Niech (x0, x1, x1, ... xk) oznacza ciąg wektorów, M, N - macierz kwadratowa,
xk+1 = Mxk + Nb, k = 0, 1, . . . (1)
Uwagi:
 promień spektralny to największa, co do modułu, wartość własna macierzy M opisującej
dany układ
 wyrażenie określone wzorem (1) przy dowolnym wektorze początkowym x0 jest zbieżne do
jedynego punktu granicznego wtedy i tylko wtedy, gdy Á(M) < 1.
Zadanie 1
Zaimplementuj własny program wyznaczający promień spektralny danej macierzy.Użyj go-
towych funkcji.
Zadanie 2
Oblicz promień spektralny podanej macierzy
2 1
A = .
4 18
Metoda Richardsona
xk+1 = xk + (b - Axk),
co jest jednoznaczne z zapisem
xk+1 = (I - A)xk + b. (2)
Metoda ta jest zbieżna, gdy promieÅ„ spektralny macierzy Á(I - A) < 1.
Metoda Jacobiego
W metodzie tej macierz A zapisuje siÄ™ jako
A = L + U + D, (3)
gdzie L, U, D są odpowiednio macierzami: dolnotrójkątną, górnotrójkątną i przekatniową .
(L + D + U)x = b
Dx = -(L + U)x = b
x = -D-1(L + U)x + D-1b
1
Metody numeryczne, dr inż. Magdalena A
apińska
Metoda ma następującą postać
xk+1 = -D-1(L + U)xk + D-1b (4)
Metoda ta jest zbieżna gdy promieÅ„ spektralny Á(-D-1(L + U)) < 1.
MacierzÄ… diagonalnie dominujÄ…cÄ… : dla 1 d" i d" n
n
|aii| e" |aij| .
j=1,j=i

Jeśli macierz A jest diagonalnie dominująca, to dla dowolnego wektora początkowego,
metoda Jacobiego tworzy ciąg zbieżny do rozwiązania układu.
Metoda Gaussa - Seidela A = L + D + U.
Po przekształceniach otrzymamy:
xk+1 = -D-1(Lxk + Uxk) + D-1b,
co dalej daje
xk+1 = (D + L)-1(-U)xk + (D + L)-1b. (5)
Metoda jest zbieżna, gdy Á((D + L)-1(-U)) < 1, a także gdy macierz A jest diagonalnie domin-
ujÄ…ca.
Zadanie 3
Czy metoda Jacobiego jest zbieżna dla
2 3
A = .
4 20
Zadanie 4
Dany jest liniowy układ równań z macierzą
ëÅ‚ öÅ‚
2 1 1
íÅ‚ Å‚Å‚
A = -1 1 -1 .
1 -1 3
Zbadaj zbieżność metody Richardsona, Gaussa Seidela, Jacobiego.
Zadanie 5
2
Metody numeryczne, dr inż. Magdalena A
apińska
Dla jakich wartości parametru ą układ
Å„Å‚
x + y + z = 1
òÅ‚
Ä…y + z = 0 .
ół
Ä…z = 0
Zadanie 6
Napisać własny program, który rozwiązuje podany układ równań metodą Jacobiego. W przy-
padku zajęć laboratoryjnych skorzystać z gotowych funkcji.
Ważne:
Á(MGS) < Á(MJ)
Jeśli obie metody są zbieżne, którą należy rekomendować? (patrz Fortuna 237)
3
Metody numeryczne, dr inż. Magdalena A
apińska
Wektory i wartości własne
Metoda potęgowa
1. i = 0 wybieramu dowolny x0 = 1 oraz ustalamy liczbÄ™ iteracji,
"
2. obliczamy wektor
vi+1 = Axi oraz mi+1 = vi+1 ,
"
jeżeli mi+1 to kończymy algorytm, inaczej
vi+1
xi+1 =
mi+1
3. jeśli i + 1 przekroczy ilość ustalonych iteracji to kończymy, jeśli nie to i = i + 1.
Gdy ciąg x0, x2, x4, . . . jest zbieżny do x to m1, m2, m3, . . . jest zbieżne do m.
xi+1 - xi 0 Ax = mx,  = m,
xi+1 - xi 2 Ax = -mx,  = -m.
"
Zadanie 1
Stosując metodę potęgową znalez
ć wektor własny oraz odpowiadającą mu wartość własną dla
îÅ‚ Å‚Å‚ îÅ‚ Å‚Å‚
-1 1 0 1
ðÅ‚ ûÅ‚ ðÅ‚ ûÅ‚
A = 1 -1 0 , gdzie x0 = -1 .
1
0 0 1
2
Zadanie 2
Stosując metodę potęgową wykonać 2 kroki iteracyjne dla
îÅ‚ Å‚Å‚
4 -1 1
ðÅ‚ ûÅ‚
A = -1 3 -2 .
1 -2 3
Zadanie 3
Napisać własny program realizujący metodę potęgową, zakładając, że użytkownik podaje macierz
A oraz wektor x0 (zakładamy, że użytkownik podał x0 dla którego metoda jest zbieżna, można
skorzystać z funkcji Dot w przypadku mnożenia macierzy).
1