Arytmetyka zmiennoprzecinkowa.

W zależności od sposobu zapisu wyróżnia się liczby:

1. stałoprzecinkowe

2. zmiennoprzecinkowe

W liczbach stałoprzecinkowych w ciągu bitów przedstawiających liczbę binarną miejsce przecinka jest umownie ustalone i nie zmienia się podczas wykonywania obliczeń.

Liczby przechowywane są w komórkach pamięci. Komórka ze stałym przecinkiem podzielona jest na trzy części. Komórka składa się z 13 bitów i ma wygląd:

znak część część

liczby całkowita ułamkowa

W przypadku liczby ujemnej wpisujemy w miejsce znaku „1”, a gdy liczba jest dodatnia „0”.

Ex.1.

Zapisz liczby w komórkach pamięci ( 13 bitowych ).

1. +1110.11011

2. - 1110.11011

3. +0.00000001

W systemie zmiennoprzecinkowym liczby dają się zapisać w postaci półalgorytmicznej

X = m * 10^c , gdzie m - mantysa; c - cecha; 10 - zasada numeracji ( p ). Liczby przechowywane są w komórkach pamięci. Komórki te składają się z czterech części i są one 13 bitowe.

znak mantysa cecha

liczby

Przecinek znajduje się tu po bicie znaku. Cecha ze znakiem wskazuje faktyczne położenie przecinka w danej liczbie.

Ex. 2

Przedstaw liczby w zapisie półalgorytmicznym:

a) X₁ = 111,01 = 11,101 * 10¹ = 1,1101 * 10¹⁰ = 0,11101 * 10¹¹

b) X₂ = 0,00101 = 0,0101 * 10^-1 = 0,101 * 10 ^-10 = 1,01 * 10 ^-11 = 10,1 * 10 ^-100 = 101 * 10 ^-101

Ex. 3.

Zapisz w komórkach pamięci ( 13 bitowych ) liczby:

1. 0,11101101 * 10¹¹

2. 
   
   0,011101101 * 10¹⁰⁰

3. 
   
   
   
   
   0,0011101101

Gdy mantysa nie mieści się to należy ją zaokrąglić. Zazwyczaj z tego powodu nakłada się ograniczenia mantysy 0,1 ≤ |m| ≤ 1.

Ten sposób zapisu liczb zmiennoprzecinkowych nazywa się zapisem znormalizowanym.

Normalizowanie liczby X = 0,011101101 * 10¹⁰⁰ = 0,11101101 * 10^{100 - 1} = 0,11101101*10¹¹

Ex. 4.

Dodaj dwie liczby o 8 bitowej mantysie i 4 bitowym wykładniku.

A = 0 00101001 1101

B = 0 00011010 1010

A_NOR = 0 10100100 1011

B_NOR = 0 11010000 0111

A = 0 10100100 1011

+ B = 0 00001101 1011

0 10110001 1011

Tak więc widzimy, żeby dodać dwie liczby należy je najpierw znormalizować, następnie zrównać cechy i dopiero dodać do siebie.

Ex. 5.

Pomnóż liczby A i B

A = 0 10000000 1001

B = 0 01000000 0011

A_NOR = 0 10000000 1001

* B_NOR = 0 10000000 +0010

0 01000000 1011

Ex. 6.

Odejmij od liczby A liczbę B

A = 0 1000000 1001

B = 1 0100000 0011

A = 0 10000000 1001

- B = 1 00000001 1001

0 01111111 1001

Widzimy, żeby odjąć dwie liczby trzeba zrównać ich cechy i odjąć mantysę.

Przedziały liczb stałoprzecinkowych zapisywanych w komórkach pamięci.

k

r l k - l - 1

Maksymalną liczbą jaką możemy zapisać w pamięci jest liczba:

1..1,1..1 = 1..1,1..1 +0,0..01 - 0,0..01 = 10..0,0..0 - 0,0..01 = 2^l - 2 ^{-(k -l - 1)}

r k-l-1 k-l-1 l +1

Minimalną liczbą jest liczba 2 ^{- ( k - l - 1 )}

Przedział liczb zapisywanych w pamięci jest następujący 2 ^{- ( k - l - 1 )} ≤ |x| ≤ 2^l - 2 ^{-(k -l - 1)}

Przedziały liczb zmiennoprzecinkowych zapisywanych w komórkach pamięci.

k

r k - r - 2

Maksymalną liczbą jaką możemy zapisać w pamięci jest liczba:

0,1..1 * 10^1..1 = ( 1,0..0 - 0,0..01 ) * 10^1..1= ( 1 - 2 ^-r ) *

r k-l-1 r

Minimalną liczbą jest liczba 2^-r * 2 ^{k - r - 2}

Przedział liczb zapisywanych w pamięci 2^-r * 2 ^{k - r - 2} ≤ |x| ≤ ( 1 - 2 ^-r ) *

Błędy obliczeń.

Niech x, y są liczbami zmiennoprzecinkowymi. Działania f (x ⊕ y ), gdzie ⊕ oznacza dowolną operację arytmetyczną, mają do pewnego stopnia inne własności niż dokładne działania arytmetyczne.

Ex. 1.

Sprawdź czy fl ( fl ( a + b ) + c ) = fl ( a + fl ( b + c )), gdy:

a = (0) 11001110 (0) 011

b = (0) 10000011 (0) 110

c = (1) 10000011 (0) 110

a = (0) 00011001 (0) 110

+ b = (0) 10000011 (0) 110

(0) 100011100 (0)110

+ c =(1) 10000011 (0)110

(0) 00011001 (0) 110 = (0) 11001000 (0) 011 = a

fl ( a + fl ( b + c )) = (0) 11001110 (0) 011

Wartością dokładną wielkości nazywamy wielkość wynikającą z definicji.

Wartością przybliżoną wielkości nazywamy wartość liczbową otrzymaną w wyniku obliczeń.

Niech X będzie wartością dokładną, a „x” przybliżoną. Błędem bezwzględnym wartości przybliżonej nazywamy każdą liczbę Δx spełniającą warunek:

| X - x | ≤ Δx

Błędem względnym wartości przybliżonej x obarczonej błędem bezwzględnym Δx nazywamy liczbę:

Ex. 2.

Niech x = 0,2. Liczba x ma w zapisie binarnym nieskończone rozwinięcie równe (0) 00110011.. Najbliższa jej liczba, którą można przedstawić stosując 5 bitową mantysę i 3 bitową cechę wynosi x = (0) 1100 (1) 10 = ( 0,187)₁₀. Oszacuj błędy.

Δx = |X - x| = 0,2 - 0,1875 = 0,0125

Typy błędów:

1. wejściowe - dane wprowadzane do maszyny odbiegają od dokładnych wartości danych

2. błędy obcięcia - powstają podczas obliczeń na skutek zmniejszenia liczby działań ( np.: przy obliczaniu szeregów matematycznych )

3. błędy zaokrągleń

Ex. 3.

Oblicz sumę liczb x₁ = 0,48; x₂ = 0,24; x₃ = 0,12. Liczby są zapisywane w komórkach pamięci 8 - bitowych * 5 bitowa mantysa, 3 bitowa cecha )

x₁ = (0) 1111 (1) 01 = 0,46875, bo (1*2^-1 + 1*2^-2 + 1*2^-3 + 1*2^-4) * 2^-1

x₂ = (0) 1111(1) 10 = 0,234375

x₃ = (0) 1111(1) 11 = 0,1171875

x₁ = (0) 1111 (1) 01

+ x₂ = (0) 0111(1) 01

(0)10110 (1) 01 = (0) 1011 (1) 00

+ x₃ = (0) 1111 (1) 11

(0) 1100 (1) 00 = (1*2^-1 + 1* 2^-2 + 0* 2^-3 + 0*2-4)*2⁰ = 0,75

Granicznym błędem bezwzględnym nazywa się najmniejszą liczbę dodatnią δ, większą od modułu błędu bezwzględnego |ε| ≤ δ.

Granicznym błędem względnym nazywa się najmniejszą liczbę δ' większą od modułu błędu bezwzględnego ε' ≤ δ.

Działanie	Błąd bezwzględny	Błąd względny
+ ( - )	δ = δ1 + δ2
*	δ = δ1*|x1| + δ2*|x2|	δ' = δ1' + δ2'
/		δ' = δ1' + δ2'

Rozwiązywanie równań nieliniowych z jedną niewiadomą.

Rozróżniamy równania:

1. algebraiczne typu W_n(x) = a₀*xⁿ + a₁*xⁿ⁺¹ + ... + a_n, gdzie W_n(x) = 0.

W takich równaniach nie można podać analitycznego rozwiązania równania o stopniu większym niż 4.

2. przestępne typu F(x) = lg(x+2) - cos x, gdzie F(x) = 0

W tego typu równaniach nie można podać analitycznego rozwiązania.

Rozwiązanie numeryczne polega na:

1. ustaleniu istnienia pierwiastków i ich liczby

2. obliczeniu pierwiastków z zadaną dokładnością i ocenie błędu

Istnieją dwie metody rozwiązania równań:

1. metody wymagające wyznaczenia tzw. przedziałów izolacji, w których się znajduje pierwiastek

2. metody wymagające przybliżenia początkowego pierwiastka

Ustalanie istnienia pierwiastków.

Jeżeli funkcja F(x) jest ciągła w przedziale [a,b] i spełnia w warunki:

1. F(a) * F(b) < 0

2. F(x) < 0 lub F(x) > 0

to przedział [a,b] jest przedziałem izolacji.

Jeżeli znaki funkcji na granicach przedziałów są takie same to wiemy, że:

1. równanie w przedziale [a,b] nie ma pierwiastków

2. równanie w przedziale [a,b] ma parzystą liczbę pierwiastków

Natomiast jeżeli znaki funkcji na krańcach przedziału są różne, to wiemy że funkcja ma w danym przedziale co najmniej jeden pierwiastek.

Aby ustalić przedziały izolacji dla pierwiastków należy, począwszy od punktu x = a badać wartość funkcji F(x), aż do punktu x = b z krokiem h, który powinien być jak najmniejszy. Jeżeli F(x) * F(x+h) < 0 to przedział [x, x+h] zawiera pierwiastek funkcji F.

Należy też sprawdzić warunek

(F(x) - F(x-h))*(F(x-h) - F(x)) > 0.

Jeżeli warunek jest nie spełniony to krok dzielimy na pół dopóki w przedziale (x-h, x+h) nie

będzie lub będą dwa pierwiastki.

Ex. 1.

Metodą dzielenia przedziałów wyznaczyć przedziały izolacji dla funkcji

x³ - 6x² + 3x + 10 = 0 , gdy x ∈ [-2; 6]

Przyjmijmy h = 1,5.

F(-2) = -12

F(-0,5) = 6,875 α₁ ∈ [ -2 ; -0,5 ]

W tym przedziale nie ma pierwiastków

F(1) = 8 lub jest ich parzysta liczba

F(2,5) = -4,375 α₂ ∈ [ 1 ; 2,5 ]

F(4) = -8

F(5,5) = 11,375 α₃ ∈ [ 4 ; 5,5 ]

Dla x = -1 przedział izolacji wynosi [ -2 ; -0,5 ]

Dla x = 2 przedział izolacji wynosi [ 1 ; 2,5 ]

Dla x = 5 przedział izolacji wynosi [ 4 ; 5,5 ]

Istnieją trzy metody badania wartości pierwiastka w przedziale izolacji z określoną dokładnością:

1. metoda połowienia

2. metoda siecznych

3. metoda stycznych

Metoda połowienia.

x₁ x₂ x₀

a₃ b₃

a₂ b₂

a₁ b₁

a₀ b₀

Założenia:

Funkcja F(x) musi być ciągła w przedziale [a₀, b₀].

F(a₀)*F(b₀) < 0 , więc funkcja na granicy przedziałów musi mieć przeciwne znaki.

W przedziale [a₀, b₀] musi być dokładnie jeden pierwiastek.

Procedura:

1. Znaleźć kolejne przedziały [a₀, b₀] ⊃ [a₁, b₁] ⊃ [a_2, b₂] ⊃ ... takie, zę każdy z nich zawiera pierwiastek równania α. Przedziały P_i = [a_i, b_i] wyznacza się rekurencyjnie w sposób:

1. wyznaczamy środek przedziału p_i-1: x_i-1 =
   

2. x_i-1 jest pierwszym przybliżeniem pierwiastka równania

3. powstają dwa przedziały [a_i-1, x_i-1] oraz [x_i-1, b_i-1]. Wybieramy ten, w którym funkcja ma przeciwne znaki na końcach przedziału

4. P_i = [a_i, b_i] utożsamiamy z wybranym przedziałem

2. Kolejne przybliżenia x_i-1 =
   dążąc do dokładnej wartości pierwiastka równania α

3. Procedurę należy powtarzać, dopóki długość kolejnego przedziału nie okaże się mniejsza od wartości ε > 0 ; | b_i - a_i | < ε, gdzie ε jest dokładnością obliczeń.

Ex. 2.

Metodą połowienia wyznaczyć pierwiastki równania x₃ - 6x₂ + 3x + 10 = 0, wiedząc że α₁ ∈ [-2; -0,5], α₂ ∈ [1; 2,5], α₃ ∈ [4; 5,5] i dokładności ε = 0,1

Pierwszy pierwiastek:

Krok 1

x₀ = 1 / 2 * ( -0,5 - 2 ) = -1,25

F(-1,25) = -5,078

F(-2) = -12

F(-0,5) = 6,875

α₁ ∈ [ 1,25 ; -0,5 ]

Obliczmy |-0,5-(-1,25)| = 0,75 > ε = 0,1

Krok 2

x₁ = ˝*(-0,5-1,25) = -0,875

F(-0,875) = 2,111

F(-1,25) = -5,078

α₂ ∈ [ -1,25 ; -0,875 ]

Obliczmy |-0,875 - (-1,25)| = 0,375 > ε = 0,1

Krok 3

x₂ = ˝*(-0,875-1,25) = -1,0625

F(-1,0625) = -1,160

F(-0,875) = 2,111

F(-1,25) = -5,078

α₃ ∈ [ -1,0625 ; -0,875 ]

Obliczmy |-0,875 - (-1,0625)| = 0,185 > ε = 0,1

Krok 4

x₃ = ˝*(-0,875-1,0625) = -0,96875

F(-0,96875) = 0,5537

F(-1,0625) = -1,160

F(-0,875) = 2,111

α₄ ∈ [ -1,0625 ; -0,96875 ]

Obliczmy |-0,96875 - (-1,0625)| = 0,09375 < ε = 0,1

Zatem naszym pierwiastkiem obliczonym z dokładnością do 0,1 jest liczba -0,96875

Metoda siecznych ( reguła falsi ).

x₀ x₀ x₀

a₁ b1

a₂ b₂

a₃ b₃

a₀ b ₀

Założenia:

Funkcja F(x) musi być ciągła w przedziale [a₀, b₀].

F(a₀)*F(b₀) < 0 , więc funkcja na granicy przedziałów musi mieć przeciwne znaki.

W przedziale [a₀, b₀] musi być dokładnie jeden pierwiastek.

Procedura:

1. Metoda ta polega na identyfikacji liniowej funkcji F(x):

1. znaleźć kolejne przedziały [a₀, b₀] ⊃ [a₁, b₁] ⊃ [a_2, b₂] ⊃ ... takie, zę każdy z nich zawiera pierwiastek równania α.

2. Przedziały P_i = [a_i, b_i] wyznacza się rekurencyjnie poprzez wyznaczenie współrzędnej punktu przecięcia prostej przechodzącej przez punkt ( a_i, F(a_i) ) i ( b_i , F(b_i))

3. wyznaczamy punkt x_i-1 =
   

4. x_i-1 jest pierwszym przybliżeniem pierwiastka równania, a następne są obliczane ze wzoru x_i-1 =
   

5. powstają dwa przedziały [a_i-1, x_i-1] oraz [x_i-1, b_i-1]. Wybieramy ten, w którym funkcja ma przeciwne znaki na końcach przedziału

6. P_i = [a_i, b_i] utożsamiamy z wybranym przedziałem

2. Kolejne przybliżenia x_i-1 dążą do dokładnej wartości pierwiastka równania α

3. Procedurę należy powtarzać, dopóki | x_i - x_i-1 | < ε, gdzie ε jest dokładnością obliczeń.

Metoda stycznych ( Newtona ).

F(x₀)

F(x₁)

F(x₂)

F(x₃)

x₁ x₂ x₃

Założenia:

Funkcja F(x) musi być ciągła w przedziale [a₀, b₀].

F(a₀)*F(b₀) < 0 , więc funkcja na granicy przedziałów musi mieć przeciwne znaki.

W przedziale [a₀, b₀] musi być dokładnie jeden pierwiastek.

Istnieje w przedziale [a₀, b₀] F'(x) i F''(x), które są różne od zera i mają stały znak.

Procedura:

1. Za początkowe przybliżenie α należy przyjąć punkt x₀, w którym spełniony jest warunek F(x₀) * F''(x­₀) > 0 ,a zatem x₀ = a₀

2. Kolejne przybliżenia obliczamy ze wzoru x_i = x_i-1 -
   

3. Kolejne przybliżenia x_i-1 liczone według wzoru x_i = x_i-1 -
   dążą do dokładnej wartości pierwiastka równania α

4. Procedurę należy powtarzać, dopóki | x_i - x_i-1 | < ε, gdzie ε jest dokładnością obliczeń.

Ex. 3.

Odnaleźć metodą stycznych pierwiastek równania F(x) = 0, gdzie F(x) = ln(x) + x-2 dla α∈[1,3] i ε = 0,01.

Badamy warunki:

F(1) = -1; F(3) = 1,098 zatem F(1) * F(3) < 0

F'(x) = 1 / x + 1 ; F''(x) = -1/x² zatem x∈[1;3] F'(x)≠0 i F''(x)≠0

Dla x∈[1;3] F'(x) > 0 a F''(x) < 0

Rozwiązanie:

Ponieważ dla x₀ = 1 F(x₀) = -1, F''(x₀) = -1, więc F(x₀) * F''(x₀) > 0, więc jako pierwsze przybliżenie pierwiastka równania α przyjmiemy x₀ = 1.

Krok 1

x₁ = x₀ -
= 1 - (-1/2 ) = 1,5

| 1 - 1,5 | = 0,5 > ε = 0,01

Krok 2

x₂ = x₁ -
= 1,5 - (-0,095/1,667 ) = 1,557

| 1,5 - 1,557 | = 0,057 > ε = 0,01

Krok 3

x₃ = x₂ -
= 1,557 - (-0,0002391/1,6927 ) = 1,557 + 0,000145 = 1,557145

| 1,557 - 1,557145 | = 0,000145 < ε = 0,01

Tak więc przyjmujemy, że α = x₃ = 1,557145 z dokładnością do ε = 0,01.

Interpolacja funkcji .

Przedstawienie funkcji polega na wyborze spośród zbioru funkcji F funkcji f, która przybliża funkcję ze zbioru F. Jednym ze sposobów wyboru funkcji przybliżającej jest interpolacja. Jako funkcje przybliżające najczęściej stosuje się wielomiany algebraiczne. Funkcję przybliżającą można przedstawić tabelarycznie lub graficznie.

Wartość cechy x	Wartość cechy y
x0 x1 : xn	y0 y1 : yn

Funkcja f jest określona w n+1 punktach zwanych węzłami interpolacyjnymi funkcji f. Jeśli zatem dla różnych x₀, x₁, ..., x_n otrzymano wartości y₀, y₁, ..., y_n, wtedy istnieje dokładnie jeden wielomian algebraiczny W(x) stopnia n, którego W(x_i) = y_i, dla i=0,1,2, ..., n.

Jako wzór wyrażający zależność y od x możemy przyjąć:

y = a₀ + a₁*x + a₂*x² + ... + a_n*xⁿ

Mając daną tabelaryczną wartość funkcji w węzłach interpolacyjnych możemy zbudować układ n+1 równań algebraicznych z n+1 niewiadomymi, którymi są współczynniki a₀, a₁,...,a_n.

y₀ = a₀ + a₁*x₀ + a₂*x₀² + ... + a_n*x₀ⁿ

y₁ = a₀ + a₁*x₁ + a₂*x₁² + ... + a_n*x₁ⁿ

^:

y_n = a₀ + a₁*x_n + a₂*x_n² + ... + a_n*x_nⁿ

Wyznacznik macierzy współczynników jest wyznacznikiem Vandermonde'a o postaci:

1 x₀ x₀^{2 ...} x₀ⁿ

D = 1 x₁ x₁^{2 ...} x₁ⁿ

: : : : :

1 x_n x_n^{2 ...} x_nⁿ

Ponieważ węzły interpolacyjne są różne, tj. x_i ≠ x_j dla i ≠ j, to zawsze wyznacznik Vandermonde'a jest różny od zera, a zatem równanie ma dokładnie jedno rozwiązanie o różnych wartościach a_i, określone wzorem Cramera:

gdzie: D_ij są kolejnymi dopełnieniami algebraicznymi elementów i- tej kolumny macierzy

współczynników.

Oznacza to, że istnieje tylko jeden wielomian W(x), który ma postać:

1. wielomianu Lagrange'a

2. wielomianu Newtona

Wielomian Lagrange'a.

Podstawiając do wzoru W(x) = a₀ + a₁*x + a₂*x² + ... + a_n*xⁿ wartości a₁ oraz dokonując grupowania otrzymujemy postać W(x) = y₀*L₀(x) + y₁*L₁(x) + ... + y_n*L_n(x), gdzie L_n(x) są wielomianami stopnia co najwyżej n.

Ponieważ w węzłach powinna zajść równość W(x_i) = y_i to wartość wielomianu we wszystkich węzłach oprócz węzła z numerami „i” powinna być równa 0, a wartość wielomianu w tym węźle powinna być równa 1, czyli:

0 , gdy i ≠ j

L_i(x_i) = 1 , gdy i = j

Aby określić funkcję L_i(x) należy znaleźć wielomian stopnia n, który w punktach

x₀, x₁, ..., x_j-1, x_j+1, ..., x_n jest równy zero, a w punkcie x_j = 1.

L_j(x) = λ*(x - x₀)*(x - x₁)* ... (x - x_j-1)*(x - x_j+1)* ... *(x - x_n)

L_j(x_j) = 1

więc λ*(x_j - x₀)*(x_j - x₁)* ... (x_j - x_j-1)*(x_j - x_j+1)* ... *(x_j - x_n) = 1, to po wyrugowaniu ( zastąpieniu innym wyrażeniem ) λ otrzymujemy wzór:

Ostatecznie wzór Newtona na wielomian interpolacyjny ma postać:

Ex. 1. Znaleźć wielomian interpolacyjny, który

1. w punktach -2,1,2,4 ma wartość 3,1,-3,8

2. w punktach 1,2,3,4,5 ma wartość 2,2,4,4,6

a)

Wielomian Newtona.

Aby wyznaczyć wielomian Newtona trzeba posłużyć się ilorazem różnicowym:

:

Ogólnie iloraz różnicowy rzędu n tworzymy za pomocą ilorazu różnicowego rzędu n-1 za pomocą wzoru:

dla n = 1,2,... oraz i = 0,1,2,... np.:

Jeżeli funkcja jest określona w n punktach x₀, x₁, ..., x_n, to wielomian algebraiczny interpolacyjny W(x) można zapisać w postaci wzoru Newtona:

W(x) = f(x₀) + f(x₀, x₁)*ω₀(x) + f(x₀, x₁, x₂)*ω₁(x) + ... + f(x₀, x₁, ..., x_n)*ω_n-1(x)

gdzie: ω_i(x) = (x - x₀) * (x - x₁) * ... * (x - x_i) dla i = 0,1,..., n-1

Ex. 2. Napisać wzór interpolacyjny dla funkcji określonej wartościami:

1. f(0) = 1 ; f(2) = 3 ; f(3) = 2 ; f(4) = 5 ; f(6) = 7

2. f(1) = 2 ; f(2) = 2 ; f(3) = 4 ; f(4) = 4 ; f(5) = 6

a)

xi	f(xi)	Iloraz 1 rzędu	Iloraz 2 rzędu	Iloraz 3 rzędu	Iloraz 4 rzędu
				f(xi, xi+1)	f(xi, xi+1,xi+2)	f(xi, xi+1,xi+2,xi+3)	f(xi, xi+1,xi+2,xi+3, xi+4)
0	1	=1
2	3	-1	-2/3	2/3
3	2	3	2	- 2/3	-2/9
4	5	1	-2/3
6	7

W(x) = 1 + 1*(x-0) - *(x-0)(x-2) + *(x-0)(x-2)(x-3) -
*(x-0)(x-2)(x-3)(x-4) =

=

b)

xi	f(xi)	Iloraz 1 rzędu	Iloraz 2 rzędu	Iloraz 3 rzędu	Iloraz 4 rzędu
				f(xi, xi+1)	f(xi, xi+1,xi+2)	f(xi, xi+1,xi+2,xi+3)	f(xi, xi+1,xi+2,xi+3, xi+4)
1	2	0
2	2	2	1	- 2/3
3	4	0	-1	2/3	1/3
4	4	2	1
5	6

W(x) = 2 + 1*(x-1)(x-2) - *(x-1)(x-2)(x-3) +
*(x-1)(x-2)(x-3)(x-4)

Aproksymacja funkcji.

Funkcję F(x) znaną lub określoną tabelą wartości będziemy aproksymować inną funkcją f(x), zwaną funkcją aproksymującą lub przybliżeniem funkcji f(x), a błędy tej operacji nazywać będziemy błędami aproksymacji. W metodach aproksymacji możemy wyróżnić następujące kroki:

1. wybór na podstawie wykresu funkcji aproksymującej f(x), która najlepiej oddaje charakter zależności między cechami X i Y

2. szukamy parametrów a, b, c, ... dla wybranej funkcji F(x)

Sposób poszukiwania parametrów dla funkcji aproksymującej określa różne metody aproksymacji, wśród których najbardziej znaną jest metoda najmniejszych kwadratów (aproksymacja średniokwadratowa).

Niech w punkcie x_i będzie dana funkcja F(x), która przyjmuje w tych punktach wartości y_i, gdzie i = 1, 2, ..., n. Będziemy poszukiwać takiej funkcji f(x) przybliżającej daną funkcję F(x), która umożliwi wygładzenie funkcji F(x), dlatego należy znaleźć taką funkcję f(x), aby był spełniony warunek:

Gdy funkcja aproksymacyjna zostanie wybrana, to podstawiamy ją do powyższego wzoru i mamy:

Funkcja P(a, b, c, ...) jest funkcją wielu zmiennych. Trzeba znaleźć takie wartości dla parametrów a, b, c, ... dla których funkcja ta osiągnie minimum. Dla ich uzyskania obliczamy pochodne cząstkowe względem każdego parametru i tworzymy układ równań:

:

:

...........................................................................................................

Aproksymacja liniowa.

Niech funkcja aproksymująca będzie funkcją f(x) = a*x + b. Mamy wtedy:

Zastosujmy wzory Cramera:

D = = n *Σx_i² - (Σx_i)²

n

D_a = = n *Σyi * xi - Σx_i * y_i

n

D_b = = Σx_i² * Σy_i - Σx_i * y_i * Σx_i

Wprowadźmy nowe zmienne:

S₁ =
; S₂ =
; S₃ =
; S₄ =

Więc mamy:

D = n*S₂ - S₁² ; D_a = n*S₄ - S₁*S₃ ; D_b = S₂*S₃ - S₄*S₁

Czyli:

Ex. 1.

Podaj funkcję aproksymującą dla danych przedstawionych w tabeli:

X	1	2	3	4	5
Y	2	5	8	8	12

S₁ = 1 + 2 + 3 + 4 + 5 = 15

S₂ = 1 + 4 + 9 + 16 + 25 = 55

S₃ = 2 + 5 + 8 + 8 +12 = 35

S₄ = 1 * 2 + 2 * 5 + 3 * 8 + 4 * 8 + 5 * 12 = 128

f(x) = 2,3 * x + 0,1

Niech funkcja aproksymująca będzie wielomianem a_n * x_n + a_n-1 * x_n-1 * ... * a₀. Musimy wtedy:

1. w wyniku podstawienia za X i Y odpowiednich wartości mamy układ n+1 równań z n+1 niewiadomymi, którego rozwiązanie możemy uzyskać z wzorów Cramera

2. w przypadku wyboru zależności aproksymującej w postaci potęgowej lub logarytmicznej powstaje nieliniowy układ równań

3. rozwiązanie nieliniowego układu równań uzyskuje się w taki sposób, że przekształcamy funkcję aproksymującą do postaci liniowej, wyznaczając parametry a_i, rozwiązując układ równań liniowych a potem wracamy do funkcji pierwotnej.

Niech y = a*x^m, gdzie a>0 i x>0

Dokonujemy przekształceń:

ln(y) = ln(a * x^m)

ln(y) = ln(a) + ln(x^m)

ln(y) = ln(a) + m* ln(x)

Niech u = ln(x) ; A = m ; B = ln(a) ; F(n) = ln(y)

Po podstawieniu otrzymujemy nowe równanie aproksymujące ( liniowe ) F(n) = A * u + B, które rozwiązujemy w tradycyjny sposób.

Ex. 2.

Wyznaczyć funkcję aproksymującą potęgową f(x) = a * x^m dla funkcji F(x) zadanej w postaci tabeli:

X	1	2	4	5
Y	4	8	16	25

u = ln(x) ; F(u) = ln(y) = v

u	ln(1) = 0	Ln(2) = 0,7	ln(4) = 1,4	ln(5) = 1,6
v	ln(4) = 1,4	Ln(8) = 2,1	ln(16) = 2,8	ln(25) = 3,2

S₁ = 0 + 0,7 + 1,4 + 1,6 = 3,7 ; S₂ = 0,49 + 1,96 + 2,56 = 5,01

S₃ = 1,4 + 2,1 + 2,8 + 3,2 = 9,5 ; S₄ = 1,47 + 3,92 + 5,12 = 10,51

y = 3,7 * x ^0,3

Niech y = a * ln(x) + b

Dokonujemy odpowiednich podstawień:

u = ln(x) ; F(u) = y ; A = a ; B = b

Po podstawieniu otrzymujemy nowe równanie aproksymujące F(u) = A*u + B

Rozwiązywanie układów algebraicznych równań liniowych.

Niech będzie dany układ n równań z n niewiadomymi:

a₁₁*x₁ + a₁₂*x₂ + ... + a_1n*x_n = b₁

a₂₁*x₁ + a₂₂*x₂ + ... + a_2n*x_n = b₂

_:

a_n1*x₁ + a_n2*x₂ + ... + a_nn*x_n = b_n

Układ ten może być zapisany w postaci macierzowej Ax = b, gdzie:

A - macierz współczynników

b - wektor wyrazów wolnych

x - wektor n niewiadomych

Metody dokładne rozwiązania układu równań.

Jeżeli rozwiązanie układu równań Ax = b polega na takim przekształceniu danych A i b, że przy założeniu dokładnie wykonywanych działań arytmetycznych po skończonej liczbie działań otrzymujemy rozwiązanie, to taką metodę rozwiązania nazywamy metodą dokładną. Do metod tych zalicza się:

• metodę wzorów Cramera

• metodę eliminacji Gaussa

• metodę Doolittle'a

• metodę eliminacji Jordana

Metody dokładne charakteryzują się małą liczbą obliczeń potrzebnych do wyznaczenia rozwiązania, lecz są one niestabilne, tj. dla zadań źle uwarunkowanych numerycznie wyznaczone rozwiązanie może być obarczone dużym błędem. Metody te także bardzo obciążają pamięć komputera, ze względu na przekształcanie macierzy A i przechowywanie początkowych wartości macierzy A i b w celu sprawdzenia obliczeń.

Metoda Gaussa.

Niech będzie dany układ równań liniowych:

a₁₁* x₁ + a₁₂* x₂ + a₁₃* x₃ + ... + a_1n* x_n = b₁

a₂₂* x₂ + a₂₃* x₃ + ... + a_2n* x_n = b₂

.......................................................................

a_n-1n-1* x_n-1 + a_n-1n* x_n = b_n-1

a_mn* x_n = b_n

Aby obliczyć niewiadome x₁, x₂, ..., x_n należy wykonać następujące czynności:

1. wyznaczamy x_n z ostatniego równania, gdzie x_n = b_n / a_mn

2. wyznaczamy x_n-1 z przedostatniego równania, gdzie x_n-1 = ( b_n-1 - a_{n-1 n}* x_n) / a_n-1n-1­

3. ogólnie dla wyznaczenia k-tej niewiadomej równania mamy wzór:

x_k = ( b_k - a_km* x_n - a_kn-1* x_n-1 - ... - a_kk+1* x_k+1) / a_kk, gdzie k = n-1, n-2, ..., 1

Ex. 1. Rozwiązać układ równań liniowych doprowadzając go najpierw do postaci trójkątnej.

x₁ + 2 * x₂ + 4 * x₃ = 3 *(-2) * (-1)

2 * x₁ + 3 * x₂ + 2 * x₃ = 2

x₁ + 2 * x₂ + 3 * x₃ = 1

eliminacja

x₁ + 2 * x₂ + 4 * x₃ = 3

x₂ + 6 * x₃ = 4

x₃ = 2

x₂ = 4 - 6 * x₃ = 4 - 12 = -8

x₁ = 3 - 2 * x₂ - 4 * x₃ = 3 + 16 - 8 = 11

x₁ = 11

x₂ = -8

x₃ = 2

Metody iteracyjne ( przybliżone ) rozwiązywania równań.

Są to metody, w których konstruuje się nieskończony ciąg wektorów, zbieżny do szukanego rozwiązania x: x⁽⁰, x⁽¹⁾, ..., x^(k), gdzie x⁽⁰⁾ jest wektorem początkowym. Na k- tym kroku kończymy obliczenia i otrzymujemy rozwiązanie przybliżone x^(k). Do metod tych zaliczamy:

• metodę Jacobiego

• metodę Gaussa - Seidla

• metodę Czebyszewa

Metody iteracyjne są bardzo stabilne i posiadają prostą organizację obliczeń.

Metoda Jacobiego ( iteracji prostej ).

Niech będzie dany układ równań liniowych:

a₁₁*x₁ + a₁₂*x₂ + ... + a_1n*x_n = b₁

a₂₁*x₁ + a₂₂*x₂ + ... + a_2n*x_n = b₂

_:

a_n1*x₁ + a_n2*x₂ + ... + a_nn*x_n = b_n

Dokonujemy przekształceń powyższego układu do postaci:

x₁= a₁₁*x₁ + a₁₂*x₂ + ... + a_1n*x_n + β₁

x₂ = a₂₁*x₁ + a₂₂*x₂ + ... + a_2n*x_n + β₂

_:

x_n = a_n1*x₁ + a_n2*x₂ + ... + a_nn*x_n + β_n

co w skrócie można zapisać:
. W postaci macierzowej układ ten zapiszemy x = A*x + b, gdzie x = [ x₁, x₂, ..., x_n ]

b = [ β₁, β₂, ..., β_n ]

gdzie x - wektor niewiadomych

b - wektor n liczb β_i

A - macierz kwadratowa współczynników α_ij

Następnie szukamy kolejnych przybliżeń x⁽⁰⁾, x⁽¹⁾, ..., rozpoczynając od wektora początkowego x⁽⁰⁾, będącego dowolnym ciągiem liczb x⁽⁰⁾ = [ x₁⁽⁰⁾, x₂⁽⁰⁾, ..., x_n⁽⁰⁾ ].

Następnie podstawiamy te początkowe wartości do poprzedniego wzoru, otrzymując wektor x⁽¹⁾, stanowiący następne przybliżenie
.

Operację tę powtarzamy uzyskując kolejne przybliżenia, takie że jeżeli spełniony jest jeden z warunków:

lub
lub

Ciąg przybliżeń x^(k) jest zbieżny ( poprzez przekształcenia układu pierwotnego zawsze można uzyskać spełnienie tego warunku ).

Proces obliczeń kończymy, gdy będzie spełniony warunek:

| x_i^(k) - x_i^(k-1) | < ε, gdzie i = 1, 2, ..., n

Ex. 2. Metodą iteracyjną rozwiązać układ równań liniowych z dokładnością do 0,0001:

x₁ = 0,1 * x₁ + 0,1 * x₂ + 0,1 * x₃ + 0,7

x₂ = 0,2 * x₁ + 0,1 * x₂ + 0,3 * x₃ + 0,4

x₃ = 0,5 * x₁ + 0,2 * x₂ + 0,1 * x₃ + 0,2

Niech x⁽⁰⁾ = 0 = [ 0; 0; 0 ]

1- sza iteracja

x₁⁽¹⁾ = ( 0,1 * 0 + 0,1 * 0 + 0,1 * 0 ) = 0,7

x₂⁽¹⁾ = ( 0,2 * 0 + 0,1 * 0 + 0,3 * 0 ) = 0,4

x₃⁽¹⁾ = ( 0,5 * 0 + 0,2 * 0 + 0,1 * 0 ) = 0,2

2- ga iteracja

x₁⁽²⁾ = ( 0,1 * 0,7 + 0,1 * 0,4 + 0,1 * 0,2 ) + 0,7 = 0,83

x₂⁽²⁾ = ( 0,2 * 0,7 + 0,1 * 0,4 + 0,3 * 0,2 ) + 0,4 = 0,6

x₃⁽²⁾ = ( 0,5 * 0,7 + 0,2 * 0,4 + 0,1 * 0,2 ) + 0,2 = 0,65

| 0,83 - 0,7 | = 0,13 > 0,0001

| 0,6 - 0,4 | = 0,2 > 0,0001

| 0,65 - 0,2 | = 0,45 > 0,001

3- cia iteracja

x₁⁽³⁾ = ( 0,1 * 0,83 + 0,1 * 0,6 + 0,1 * 0,65 ) + 0,7 = 0,908

x₂⁽³⁾ = ( 0,2 * 0,83 + 0,1 * 0,6 + 0,3 * 0,65 ) + 0,4 = 0,821

x₃⁽³⁾ = ( 0,5 * 0,83 + 0,2 * 0,6 + 0,1 * 0,65 ) + 0,2 = 0,8

| 0,908 - 0,83 | = 0,078 > 0,0001

| 0,821 - 0,6 | = 0,221 > 0,0001

| 0,8 - 0,65 | = 0,15 > 0,0001

Widzimy więc że iterację powinniśmy kontynuować dalej.

23

0

1

1

0

0

0

0

0

0

0

0

0

0

0

0

0

0

1

0

1

1

0

1

1

0

1

1

1

0

0

0

1

1

0

1

1

0

1

1

1

0

0

0

0

1

0

1

1

0

1

1

1

01

0

0

1

0

0

1

1

0

1

1

1

0

0

1

0

0

0

1

1

0

1

1

1

0

0

Y

y₁

y₀

y₃

x₀ x₁ x_{2 X}

b)

---