Metody numeryczne w elektrotechnice.doc

METODY NUMERYCZNE W ELEKTROTECHNICE

Metody numeryczne – dział matematyki stosowanej, zajmujący się opracowywaniem i badaniem metod przybliżonego rozwiązywania problemów obliczeniowych w modelach matematycznych innych dziedzin nauki

Przykładowe zastosowania:

·         elektrotechnika – obliczanie parametrów obwodów elektrycznych

·         medycyna – tomografia komputerowa, opracowywanie nowych leków

·         chemia – konstruowanie nowych cząsteczek

·         inżynieria – przemysł samochodowy i lotniczy

·         informatyka – konstruowanie nowych procesorów

W obrębie klasycznych metod numerycznych możemy wyróżnić m.in. takie zagadnienia jak:

·         analiza błędów zaokrągleń

·         interpolacja

·         aproksymacja

·         rozwiązywanie równań i układów równań nieliniowych

·         całkowanie i różniczkowanie numeryczne

·         rozwiązywanie układów równań liniowych

·         obliczanie wartości własnych i wektorów własnych macierzy

·         rozwiązywanie zagadnień dla równań różniczkowych zwyczajnych i cząstkowych

·         rozwiązywanie równań całkowych i układów równań całkowych

(każdy wynik musi podlegać weryfikacji!)

Reprezentacja liczb w maszynie cyfrowej

Liczby całkowite (stałopozycyjne = stałoprzecinkowe):

, gdzie ei = 0 lub 1

Jeżeli rejestr ma d-bitów, wówczas liczba całkowita n może zawierać się w przedziale

-2d-1 < n < 2d-1-1

przykład: Zapisać liczbę 18 w systemie dwójkowym:

, może być zatem przechowywana w słowie o długości D + 1 > 5 bitów jako

Liczby rzeczywiste (zmiennopozycyjne):

,                            gdzie ½ < m < 1,  m-mantysa, i-cecha

W maszynie cyfrowej mantysa zapisywana jest w t-bitach mt

w wyniku zaokrąglenia do t-bitów mantysy

Zmiennopozycyjna reprezentacja liczby rzeczywistej x oznaczana jest symbolem rd(x) i jest równa

Nie prowadzi się operacji na małych liczbach, co oznacza, że:

,              gdzie

liczbę 2-t nazywamy dokładnością maszynową

przykład: Liczba 18,5 daje się przedstawić w postaci:

może być więc przechowywana w słowie o długości d + 1 > 11 bitów o t > 6 bitach mantysy:

0,5781525

W sytuacji, gdy elementy macierzy są < 1, np. mV, musimy wtedy dokonać przeskalowania całego układu (np. poprzez pomnożenie macierzy przez jakąś liczbę).

Błędy obliczeń

Przy obliczeniach wykonywanych na maszynach cyfrowych spotyka się trzy podstawowe rodzaje błędów:

·         błędy wejściowe (danych wejściowych) – występujące, gdy dane wprowadzane do pamięci maszyny cyfrowej odbiegają od dokładnych wartości tych danych. Źródłem tych błędów jest najczęściej skończona długość słów binarnych reprezentujących liczby i w związku z tym nieuniknione jest wstępne ich zaokrąglenie

·         błędy odcięcia – powstają podczas obliczeń na skutek zmniejszenia liczby działań, na przykład przy obliczaniu sum nieskończonych. Chcąc obliczyć wartość wyrażenia ex równego szeregowi: zastępuje je sumą częściową o odpowiednio dobranej wartości N:             

Jeżeli liczba N będzie niedostatecznie duża, to uzyskana w ten sposób wartość liczby ex będzie obliczona niedokładnie, a popełniony w ten sposób błąd jest właśnie błędem odcięcia. Błędy tego typu powstają też często przy obliczaniu wielkości będących granicami. Podobnie zastąpienie wartości pochodnej funkcji jej ilorazem różnicowym powoduje powstanie błędu odcięcia. W wielu przypadkach daje się uniknąć błędu wejściowego i odcięcia przez ograniczenie danych.

Lemat Wilkinsona:

Błędy zaokrągleń powstające podczas wykonywania działań zmiennopozycyjnych są równoważne zastępczemu zaburzeniu liczb, na których wykonujemy działania. W przypadku działań arytmetycznych otrzymujemy:

gdzie εi są co do modułu niewiększe niż dokładność maszyny ε. Przedrostek fl oznacza, że są to wyniki działań wyznaczone przy użyciu maszyny cyfrowej.

Oszacowanie błędów w obliczeniach iteracyjnych:

Wiele algorytmów obliczeniowych polega na wyznaczeniu ciągu liczb zbieżnego do poszukiwanej wartości.

Przykład:

wyznaczyć wartość funkcji , przekształcając do równania iteracyjnego. Można to uczynić obliczając ciąg y0, y1, y2..., gdzie y0 jest dowolnie wybraną liczbą, natomiast każdy element ciągu yi jest dany wzorem:

, dla i = 1, 2, 3, ...

(niewiadoma musi być po obu stronach równania)

, współczynnik przed funkcją (tutaj 1) musi być < 1 dlatego:

- iteracja i-ta

np. takiego równania nie da się rozwiązać bo 7/2

ale można zrobić tak:

jeśli założyć, że działania wykonywane są dokładnie, to ciąg y0, y1, y2, ... będzie zbieżny do liczby x, ponieważ , to

, a ciąg  po > 0

, przy i = 1, 2, 3, ... jest zbieżny do 1

Przykład:

rozwiązanie iteracyjne

wszystkie składniki przy niewiadomych są < 1  (7/8, -7/8, 3/5)

przyjmujemy dowolnie xi = 1, yi = 2

Działania potrzebne do wyznaczania kolejnych wartości ciągu y0, y1, y2, ... nazywamy iteracją. Informację o tym czy w kolejnej iteracji nastąpiło przybliżenie do rozwiązania uzyskujemy obliczając wyrażenie:

W przypadku dokładnych działań, gdy i , więc qi < 0 dla i = 1, 2, 3, ... jeśli pi>1/3. Oznacza to, że maleje wartość bezwzględna różnicy odpowiednio dużego numeru iteracji i.

Dla obliczeń wykonywanych na maszynie cyfrowej, mamy:

, gdzie , k = 1, 2, 3, ...

Dla liczby uzyskamy

Jeżeli yi jest już dostatecznie dobrym przybliżeniem liczby , a więc pi jest bliskie jedności, to pierwszy składnik powyższego wyrażenia ma pomijalnie małą wartość, natomiast drugi ze składników wynika z błędów zaokrągleń i może mieć tym większą wartość im bliższe jedności jest pi.

Przykład: dla liczby 4  x=4

Algorytm:

zmienne rzeczywiste x, y, eps

y:= x/4;                                                                      {pierwsze przybliżenie}

repeat

  y:= 0,5*(y+(x/y));

until abs (x-sqr(y))<=eps              {eps jest zakładaną dokładnością obliczeń)

Uwarunkowanie zadania i stabilność algorytmów.

              Załóżmy, że mamy skończoną liczbę danych rzeczywistych, x = ( x1, x2, ... xn ), na ich podstawie chcemy obliczyć skończenie wiele wyników rzeczywistych y = ( y1, y2, ... ym ). Będziemy więc chcieli określić wartość y według odwzorowania y = φ (x), gdzie j: D → Rm jest ciągłym odwzorowaniem i D Í Rm.

Algorytm to jednoznaczny przepis obliczania wartości odwzorowania φ (x) składający się ze skończonej liczby kroków.

Jeśli zadanie rozwiązujemy numerycznie to zamiast dokładnymi wartościami x1, x2, ... xn posługujemy się reprezentacjami rd (x1), rd (x2), ..., rd (xn). Operacje elementarne nie są więc realizowane dokładnie tylko przez odwzorowanie zastępcze fl. Ta niewielka zmiana danych powoduje, że różne algorytmy rozwiązania tego samego zadania dają na ogół niejednakowe wyniki. Dużą rolę odgrywa tu przenoszenie błędów zaokrągleń. Często niewielkie zmiany danych powodują duże względne zmiany rozwiązania zadania. Zadanie takie nazywamy źle uwarunkowanym. Wielkości charakteryzujące wpływ zaburzeń danych na zaburzenia rozwiązania nazywamy wskaźnikami uwarunkowania zadania.

Przykład:

Zerami tego wielomianu będą liczby naturalne 1, 2, ..., 20. Gdy zakłócimy np. a19 = - 210 i jego wartość wynosi a19(ε) = - (210 + 2-23), czyli a19 (ε) = a19 (1+ε). Otrzymujemy wtedy wielomian wε(x) = w (x) – 2-23, który posiada już pierwiastki zespolone i np. najbliższe pierwiastkowi 15 wielomianu w(x) są pierwiastki 13,992358137 ± 2,518830070j.

Metodę badania przenoszenia błędów można rozbudować do analizy różniczkowej błędów algorytmu.

Niech δx1 = rd (xi) – xi dla i = 1, 2, ..., n

                            dla j = 1, 2, ..., m

We wzorze tym, czynnikiem określającym wrażliwość yj na bezwzględną zmianę δxi jest

Analogiczny wzór można wyprowadzić dla przenoszenia się błędów względnych. Jeśli dla j = 0,1, 2, ..., m i dla i = 1, 2, ..., n to

,   gdzie nazywamy wskaźnikiem uwarunkowania. Jeśli wskaźniki uwarunkowania co do wartości bezwzględnej są duże to zadanie jest źle uwarunkowane.

Przykład:

Badamy uwarunkowanie sumy y = a + b + c

= , gdzie ε jest

największą z wartości ε1, ε2 i ε3, gdzie jest wskaźnikiem uwarunkowania zadania.

Stabilność numeryczna algorytmów

              Algorytm jest stabilny, jeżeli posiada tę własność, że małe błędy powstałe w pewnym kroku algorytmu nie są powiększane w innych krokach oraz nie powodują poważnego ograniczenia dokładności wszystkich obliczeń. Oznacza to, że algorytm jest numerycznie stabilny, gdy zwiększając dokładność obliczeń można wyznaczyć (z dowolną dokładnością) istniejące rozwiązanie zadania. Numeryczną stabilność zadania łatwo sprawdzić rozwiązując zadanie raz z dokładnością np. 10-6, a potem z dokładnością 10-12.

INTERPOLACJA:

...