O rozwiązywaniu zdegenerowanych i źle uwarunkowanych układów liniowych równań algebraicznych. Rozwiązywanie źle uwarunkowanych układów liniowych równań algebraicznych. Rozwiązywanie równań nieliniowych i układów równań nieliniowych

8.2.3. Systemy zdegenerowane i źle uwarunkowane

Wróćmy jeszcze raz do SLAE Ax=b z macierzą kwadratową A o rozmiarze MxN, co w odróżnieniu od rozważanego powyżej „dobrego” przypadku (patrz rozdział 8. D) wymaga specjalnego podejścia. Zwróćmy uwagę na dwa podobne typy SLAE:

• układ zdegenerowany (z wyznacznikiem zerowym |A|=0);
• układ słabo uwarunkowany (wyznacznik A nie jest równy zero, ale liczba warunku jest bardzo duża).

Pomimo tego, że tego typu układy równań znacznie różnią się od siebie (dla pierwszego nie ma rozwiązania, ale dla drugiego jest tylko jedno), z praktycznego punktu widzenia komputera, istnieje między nimi wiele wspólnego ich.

Zdegenerowane SLAE

System zdegenerowany to układ opisany macierzą z wyznacznikiem zerowym |A|=0 (macierz osobliwa). Ponieważ niektóre równania zawarte w takim układzie są reprezentowane przez liniową kombinację innych równań, to w rzeczywistości sam układ jest niedookreślony. Łatwo zdać sobie sprawę, że w zależności od konkretnego typu wektora prawej strony b istnieje albo nieskończona liczba rozwiązań, albo nie ma ich wcale. Pierwsza opcja sprowadza się do skonstruowania pseudorozwiązania normalnego (czyli wybrania z nieskończonego zbioru rozwiązań tego, które jest najbliższe pewnemu, np. zerowi, wektorowi). Sprawa ta została szczegółowo omówiona w rozdziale. 8.2.2 (patrz wykazy 8.11-8.13).

Ryż. 8.7. Graficzne przedstawienie niespójnego układu dwóch równań z pojedynczą macierzą

Rozważmy drugi przypadek, gdy SLAE Aх=b z osobliwą macierzą kwadratową A nie ma jednego rozwiązania. Przykład takiego problemu (dla układu dwóch równań) pokazano na rys. 8.7, w którego górnej części wprowadzono macierz A i wektor b oraz podjęto próbę (nieudaną, gdyż macierz A jest osobliwa) rozwiązania układu za pomocą funkcji izolowania. Z wykresu zajmującego główną część rysunku wynika, że ​​dwa równania definiujące układ wyznaczają dwie równoległe linie na płaszczyźnie (x0,xi). Linie nie przecinają się w żadnym punkcie płaszczyzny współrzędnych, w związku z czym układ nie ma rozwiązania.

NOTATKA

Po pierwsze, należy zauważyć, że SLAE zdefiniowany przez nieosobliwą macierz kwadratową o wymiarach 2x2 definiuje parę przecinających się linii w płaszczyźnie (patrz rysunek 8.9 poniżej). Po drugie, warto powiedzieć, że gdyby układ był spójny, to geometryczną reprezentacją równań byłyby dwie pokrywające się linie opisujące nieskończoną liczbę rozwiązań.

Ryż. 8.8. Wykres przekrojów funkcji resztowej f (x) = |Ax-b|

Łatwo się domyślić, że w rozpatrywanym pojedynczym przypadku pseudorozwiązań układu minimalizujących rozbieżność |Ax-b| , będzie ich nieskończenie wiele i będą leżały na trzeciej prostej, równoległej do dwóch pokazanych na ryc. 8,7 i znajduje się pośrodku między nimi. Jest to zilustrowane na ryc. 8.8, który pokazuje kilka sekcji funkcji f(x) = = | Ax-b | , które wskazują na obecność rodziny minimów o tej samej głębokości. Jeśli do ich znalezienia spróbujesz użyć wbudowanej funkcji Minimalizuj, jej metoda numeryczna zawsze znajdzie dowolny punkt wspomnianej prostej (w zależności od warunków początkowych). Zatem, aby wyznaczyć rozwiązanie jednoznaczne, należy z całego zbioru pseudorozwiązań wybrać to, które ma najmniejszą normę. Możesz spróbować sformułować ten wielowymiarowy problem minimalizacji w programie Mathcad, używając kombinacji wbudowanych funkcji Minimalizuj, ale bardziej efektywnym sposobem byłoby użycie regularyzacji (patrz poniżej) lub dekompozycji macierzy ortogonalnej (patrz sekcja 8.3).

Źle uwarunkowane systemy

Układ słabo uwarunkowany to układ, w którym wyznacznik A nie jest równy zero, ale numer warunku |A -1 | |A| bardzo duży. Pomimo tego, że źle uwarunkowane systemy posiadają unikalne rozwiązanie, w praktyce często nie ma sensu szukać takiego rozwiązania. Rozważmy właściwości źle uwarunkowanych SLAE na dwóch konkretnych przykładach (Listing 8.14).

Listowanie 8.14. Rozwiązanie dwóch bliskich, źle uwarunkowanych SLAE

Każdy wiersz Listingu 8.14 zawiera rozwiązanie dwóch bardzo bliskich, źle uwarunkowanych SLAE (z tą samą prawą stroną b i nieco innymi macierzami A). Pomimo bliskości, dokładne rozwiązania tych systemów okazują się bardzo odległe od siebie. Należy zauważyć, że dla układu dwóch równań dokładne rozwiązanie jest łatwe do uzyskania, jednak przy rozwiązywaniu wielowymiarowego SLAE drobne błędy zaokrągleń, które nieuchronnie kumulują się podczas obliczeń (w tym przez „dokładny” algorytm Gaussa) prowadzą do ogromnych błędów w wyniku. Powstaje pytanie: czy jest sens szukać rozwiązania numerycznego, jeśli z góry wiadomo, że ze względu na niestabilność samego problemu może okazać się ono całkowicie błędne?

Kolejna okoliczność, która zmusza nas do poszukiwania specjalnych metod rozwiązywania źle uwarunkowanych SLAE (nawet układu dwóch równań podanego jako przykład na Listingu 8.14) wiąże się z ich fizyczną interpretacją jako wyników eksperymentalnych. Jeśli początkowo wiadomo, że dane wejściowe otrzymano z pewnym błędem, to rozwiązywanie układów źle uwarunkowanych nie ma w ogóle sensu, gdyż małe błędy w modelu (macierz A i wektor b) prowadzą do dużych błędów w rozwiązaniu. Problemy o takich właściwościach nazywane są źle postawionymi.

Aby lepiej zrozumieć przyczynę niepoprawności, warto porównać graficzną interpretację dobrze (rysunek 8.9) i słabo (rysunek 8.10) uwarunkowanego układu dwóch równań. Rozwiązanie układu ilustruje punkt przecięcia dwóch prostych reprezentujących każde z równań.

Ryż. 8.9. Wykres dobrze uwarunkowanego układu dwóch równań

Ryż. 8.10. Wykres źle uwarunkowanego układu dwóch równań

Z ryc. 8.10 jasne jest, że linie proste odpowiadające źle uwarunkowanemu SLAE znajdują się blisko siebie (prawie równolegle). Pod tym względem niewielkie błędy w lokalizacji każdej z linii mogą prowadzić do znacznych błędów w lokalizacji punktu ich przecięcia (rozwiązania SLAE), w przeciwieństwie do przypadku układu dobrze uwarunkowanego, gdy małe błędy w nachylenie linii ma niewielki wpływ na położenie ich punktu przecięcia (ryc. 8.9).

NOTATKA

Słabe kondycjonowanie matrycy jest również typowe przy rekonstrukcji danych eksperymentalnych określonych przez nadokreślone (niespójne) SLAE (na przykład w problemach z tomografią). Tak jest w przypadku przedstawionym w następnej sekcji (patrz Listing 8.16 poniżej).

Metoda regularyzacji

Aby rozwiązać źle postawione problemy, w szczególności zdegenerowane i źle uwarunkowane SLAE, opracowano bardzo skuteczną technikę zwaną regularyzacją. Polega ona na uwzględnieniu dodatkowej informacji apriorycznej o strukturze rozwiązania (wektor oszacowania apriorycznego xo), która bardzo często występuje w praktycznych przypadkach. Z uwagi na fakt, że regularyzacja została szczegółowo omówiona w rozdz. 6.3.3 przypominamy jedynie, że problem rozwiązania SLAE Ax=b można zastąpić problemem znalezienia minimum funkcjonału Tichonowa:

Ω (x, λ) = |Ax-b| 2 + λ |x-x0| 2. (8.3)

Tutaj R jest małym dodatnim parametrem regularyzacji, który należy dobrać w jakiś optymalny sposób. Można wykazać, że problem minimalizacji funkcjonału Tichonowa można z kolei sprowadzić do rozwiązania innego SLAE:

(A T A+ λ I)-x=A T B+λ x0, (8.4)

która o godz λ ->0 przechodzi do pierwotnego źle uwarunkowanego układu i dla dużego x, będąc dobrze uwarunkowanym, ma rozwiązanie x 0. Oczywiście optymalna będzie pewna pośrednia wartość A, ustanawiająca pewien kompromis pomiędzy akceptowalną warunkowością a bliskością pierwotnego problemu. Należy zauważyć, że podejście regularyzacyjne sprowadza źle postawiony problem do warunkowo dobrze postawionego (według Tichonowa) problemu znalezienia rozwiązania układu (8.4), który ze względu na liniowość problemu jest jednoznaczny i stabilny.

Przedstawmy bez zbędnych komentarzy uregulowane rozwiązanie układu zdegenerowanego, które przedstawiono na rys. 8.8. Listing 8.15 pokazuje znalezienie rozwiązania problemu (8.4), a wynikającą z tego zależność reszty i samego rozwiązania od parametru regularyzacji R pokazano na rys. Odpowiednio 8,11 i 8,12. Należy podkreślić, że rozwiązania układu pierwotnego, a co za tym idzie układu (8.4) przy λ =0 nie istnieje.

Listing 8.15 Regularyzacja zdegenerowanego SLAE

Ostatnim krokiem regularyzacji jest wybór optymalnego λ . Istnieją co najmniej dwa rozważania, na podstawie których można wybrać parametr regularyzacji na podstawie zależności reszty od niego. W rozważanym przykładzie stosujemy kryterium ustalania λ , w oparciu o wybór normy rezydualnej równej apriorycznej ocenie błędów w określeniu danych wejściowych: macierzy A i wektora b, czyli wartości | δA | + |5λ|. Na przykład możesz wybrać normę resztkową i odpowiednio parametr λ i rozwiązanie x( λ ), które zaznaczono na rys. Linie przerywane 8.11 i 8.12.

NOTATKA 1

Inny wybór λ , która nie wymaga apriorycznych rozważań na temat błędów modelu, jest tzw. metodą quasi-optymalną, opisaną w podrozdziale. 6.3.3.

UWAGA 2

Warto sprawdzić, czy wzór (8.4) w przypadku problemu liniowego daje taki sam wynik jak wzór ogólny (8.3). Aby to zrobić, wystarczy zmienić ostatnią linię z Listingu 8.15, która wyraża rozwiązanie SLAE (8.4), na kod realizujący minimalizację metodą numeryczną, jak pokazano na Listingu 8.16. Obliczenia (które wymagają znacznie więcej czasu komputera) dają taki sam wynik, jak pokazano na rys. 8.11 i 8.12.

UWAGA 3

Spróbuj w obliczeniach z Listingów 8.15 i 8.16 przyjąć inne, na przykład bardziej realistyczne, oszacowanie a priori rozwiązania (zamiast użytego w nich wektora zerowego x0) i zobacz, jak to wpłynie na wynik.

Ryż. 8.11. Zależność reszty uregulowanego rozwiązania zdegenerowanego SLAE od parametru A. (kontynuacja Listingu 8.15)

UWAGA 4

Interesujące jest również zastosowanie zamiast wzoru (8.3) innej zależności jako funkcjonału Tichonowa: Ω(x,λ ) = |Ax-b|+ λ |x-x0 | . Odpowiedni przykład obliczeń znajdziesz na płycie CD.

Ryż. 8.12. Rozwiązanie uregulowane w zależności od λ (kontynuacja z Listingu 8.15)

Listowanie 8.16. Regularyzacja SLAE za pomocą algorytmu minimalizacji (kontynuacja Listingu 8.15)

Wymagany wektor

Jeżeli , to układ (1) nazywany jest źle uwarunkowanym. W takim przypadku błędy we współczynnikach macierzy i prawej stronie lub błędy zaokrągleń w obliczeniach mogą znacznie zniekształcić rozwiązanie.

Przy rozwiązywaniu wielu problemów znana jest w przybliżeniu prawa strona układu (1) i współczynniki macierzy A. W tym przypadku zamiast dokładnego układu (1) mamy jakiś inny układ

takie, że

Zakładamy, że wartości i d są znane.

Ponieważ zamiast układu (1) mamy układ (2), możemy znaleźć jedynie przybliżone rozwiązanie układu (1). Metoda konstrukcji przybliżonego rozwiązania układu (1) musi być stabilna na niewielkie zmiany danych początkowych.

Pseudorozwiązaniem układu (1) jest wektor minimalizujący rozbieżność na całej przestrzeni.

Niech x 1 będzie jakimś ustalonym wektorem z , zwykle określonym w opisie problemu.

Rozwiązanie układu (1) normalnego względem wektora x 1 jest pseudorozwiązaniem x 0 z normą minimalną, czyli

gdzie F jest zbiorem wszystkich pseudorozwiązań układu (1).

Ponadto

gdzie ¾ są składowymi wektora x.

Dla każdego układu typu (1) istnieje rozwiązanie normalne i jest ono unikalne. Problem znalezienia normalnego rozwiązania dla źle uwarunkowanego układu (1) jest źle postawiony.

Aby znaleźć przybliżone rozwiązanie normalne układu (1), używamy metody regularyzacji.

Według tej metody konstruujemy funkcjonał wygładzający formę

i znajdź wektor minimalizujący tę funkcjonalność. Co więcej, parametr regularyzacji a jest jednoznacznie określany na podstawie warunku

Gdzie .

Zdegenerowane i źle uwarunkowane systemy mogą być nie do odróżnienia w ramach danej dokładności. Jeżeli jednak istnieje informacja o rozwiązywaniu układu (1), to zamiast warunku (5) należy zastosować warunek:

składniki wektory są rozwiązaniami układu liniowych równań algebraicznych, które otrzymuje się z warunku na minimum funkcjonału (4)

i wygląda

gdzie E jest macierzą jednostkową,

¾Hermitowska macierz sprzężona.

W praktyce wybór wektora wymaga dodatkowych rozważań. Jeśli ich nie ma, przyjmij =0.

Dla =0 zapisujemy system (7) w postaci

Gdzie

Znaleziony wektor będzie przybliżonym rozwiązaniem normalnym układu (1).

Skupmy się na wyborze parametru a. Jeśli a=0, to układ (7) staje się układem źle uwarunkowanym. Jeśli a jest duże, to system (7) będzie dobrze uwarunkowany, ale uregulowane rozwiązanie nie będzie bliskie pożądanemu rozwiązaniu systemu (1). Dlatego zbyt duże lub zbyt małe a nie jest odpowiednie.

Zwykle w praktyce obliczenia przeprowadza się z liczbą wartości parametru a. Na przykład,

Dla każdej wartości a znajdź element, który minimalizuje funkcjonał (4). Za pożądaną wartość parametru regularyzacji przyjmuje się liczbę a, dla której równość (5) lub (6) jest spełniona z wymaganą dokładnością.

III. ĆWICZENIA

1. Zbudować układ liniowych równań algebraicznych składający się z trzech równań z trzema niewiadomymi, których wyznacznik ma wartość rzędu 10 -6.

2. Skonstruuj drugi system, podobny do pierwszego, ale posiadający inne wolne terminy, różniące się od wolnych terminów pierwszego systemu o 0,00006.

3. Rozwiązywać skonstruowane układy metodą regularyzacji (przy założeniu =0 i d=10 -4) oraz inną metodą (np. metodą Gaussa).

4. Porównaj uzyskane wyniki i wyciągnij wnioski na temat przydatności zastosowanych metod.

IV. FORMUŁA RAPORTU

W raporcie należy przedstawić:

1. Tytuł pracy.

2. Opis problemu.

3. Opis algorytmu (metody) rozwiązania.

4. Tekst programu wraz z opisem.

5. Wyniki programu.

LISTA BIBLIOGRAFICZNA

1. Tichonow A.N., Arsenin V.Ya. Metody rozwiązywania źle postawionych problemów. - M.: Nauka, 1979. 286 s.

2. Bakhvalov N.S., Zhidkov N.P., Kobelkov G.M. Metody numeryczne. - M.: BINOM. Laboratorium Wiedzy, 2007 636 s.

Praca laboratoryjna nr 23

Dane wyjściowe kolekcji:

ROZWIĄZANIE ŹLE UWARUNKOWANYCH, RZADKICH UKŁADÓW LINIOWYCH RÓWNAŃ ALGEBRAICZNYCH Z WYKORZYSTANIEM PODprzestrzeni Kryłowa

Gusiewa Julia Siergiejewna

student Samara State Aerospace University imienia S.P. Królowa,

Skrzydlak

E-mail:

Gogolewa Zofia Juriewna

Profesor nadzwyczajny Samara State Aerospace University imienia S.P. Królowa,

Skrzydlak

E-mail:

Wstęp

Modele matematyczne wielu problemów praktycznych prowadzą do rozwiązania SLAE z dużymi i rzadkimi macierzami współczynników, w których większość elementów jest równa zeru. Przypisanie macierzy rzadkości jest równoznaczne z stwierdzeniem istnienia algorytmu wykorzystującego jej rzadkość. Kiedy duża część współczynników macierzy składa się z zer, jest całkiem oczywiste, że nie chcielibyśmy przechowywać wszystkich tych zer w pamięci komputera. Dlatego algorytmy macierzowe muszą być zaprojektowane w taki sposób, aby przetwarzane były tylko elementy niezerowe i aby w oparciu o wcześniejszą wiedzę o położeniu elementów niezerowych unikano operacji takich jak dodawanie przez zero lub mnożenie przez zero. Zatem liczba operacji wykonywanych przez maszynę podczas wykonywania algorytmu jest proporcjonalna do liczby niezerowych elementów, a nie do liczby wszystkich elementów macierzy. Poważnym problemem podczas pracy z rzadkimi macierzami jest stabilność numeryczna.

Kiedy metody takie jak eliminacja Gaussa wymagają zbyt dużo czasu lub pamięci do rozwiązania układów równań, stosuje się metody iteracyjne. Rozwiązując źle uwarunkowane, rzadkie SLAE, konieczne staje się wybranie metody, która pozwoli uzyskać dokładny wynik i najmniejsze wypełnienie (pojawienie się nowych niezerowych elementów) podczas rozwiązywania. Najbardziej efektywnymi i stabilnymi spośród iteracyjnych metod rozwiązywania takich układów równań są tzw. metody projekcyjne, a zwłaszcza ich klasa związana z rzutowaniem na podprzestrzenie Kryłowa. Metody te mają szereg zalet: są stabilne, pozwalają na wydajną równoległość, pracują z różnymi formatami wierszy (kolumn) i różnymi typami prekondycjonerów.

Sformułowanie problemu

Rozważmy układ liniowych równań algebraicznych

Gdzie: - źle uwarunkowana rzadka macierz,

.

W artykule przedstawiono analizę porównawczą iteracyjnych metod rozwiązywania źle uwarunkowanych, rzadkich SLAE. Wybrano następujące metody: metodę gradientu sprzężonego (CG), metodę minimalnych reszt (MinRes), metodę podwójnego kierunku koniugatu (CGS) oraz metodę reszt quasi-minimalnych (QMR).

Wybierając tę ​​czy inną metodę rozwiązywania SLAE, należy wziąć pod uwagę strukturę macierzy A. Wynika to z faktu, że nie każda metoda pozwala uzyskać gwarantowany wynik dla określonego układu równań liniowych.

Tym samym kryterium porównania iteracyjnych metod rozwiązywania SLAE będą: błąd wyników, szybkość zbieżności oraz struktura macierzy.

Wyniki badań numerycznych wykazały, że do rozwiązywania SLAE z macierzą A, która jest symetryczna/asymetryczna i dobrze uwarunkowana do równań normalnych, lepiej jest zastosować metodę CG. Jeżeli macierz A jest symetryczna i słabo uwarunkowana, wówczas najlepszą zbieżność wykazała metoda MinRes. Dla A – asymetrycznego, źle uwarunkowanego – metoda reszt quasi-minimalnych.

Aby poprawić współczynnik zbieżności metod iteracyjnych, stosuje się wstępne warunkowanie macierzy systemu. Polega na tym, że taką macierz kondycjonowania dobiera się tak, aby procedura rozwiązywania SLAE nie była zbyt pracochłonna i stabilna numerycznie. Właściwy wybór kondycjonera, w zależności od konkretnego problemu, może znacznie przyspieszyć konwergencję. W rzeczywistości dobry warunek wstępny jest często niezbędny, aby metoda iteracyjna w ogóle osiągnęła zbieżność.

W artykule rozważano kilka rodzajów wstępnego kondycjonowania metody quasi-minimalnych reszt z rzadkimi źle uwarunkowanymi macierzami: lewe i prawe kondycjonowanie z wykorzystaniem rozkładu QR, lewe i prawe kondycjonowanie z wykorzystaniem rozkładu LU, a także z wykorzystaniem modyfikacji rozkładu LU .

Tabela 1.

Porównanie błędu względnego warunków wstępnych

Matryca	LU- rozkład		LU- rozkład (modyfikacja)	QR- rozkład
	(lewy)	(Prawidłowy)		(lewy)	(Prawidłowy)

Wniosek

W artykule rozważono metodę reszt quasi-minimalnych w odniesieniu do rozwiązywania rzadkich, źle uwarunkowanych SLAE i różne możliwości wyboru kondycjonera. Najlepszy wynik pod względem stabilności numerycznej dała metoda reszt quasi-minimalnych, polegająca na zastosowaniu kondycjonera uzyskanego poprzez modyfikację rozkładu LU.

Bibliografia:

1. Golub J., Van Loon Ch. Obliczenia macierzowe / wyd. V.V. Wojwodina. - M.: "Mir", 1999. - 548 s.

2. Demmel J. Obliczeniowa algebra liniowa. Teoria i zastosowania / Tłum. z angielskiego H.D. Ikramowa. - M.: „Mir”, 2001. - 430 s.

3. Pissanetski S. Technologia macierzy rzadkich / wyd. HD Ikramova - M.: „Mir”, 1988. - 410 s.

4.Stankiewicz, I.V. Przechowywanie i wykorzystanie macierzy rzadkich w technologii elementów skończonych. Czasopismo „Nauka i Edukacja”. - 2005. - 10 października.

5. Tewarson R. Macierze rzadkie / wyd. HD Ikramowa. - M.: „Mir”, 1977. - 172 s.

6.Bucker Martin, Basermann Achim. Porównanie QMR, CGS i TFQMR na maszynie z pamięcią rozproszoną / Bucker Martin //Matematyka obliczeń. - 1994 - 31 maja

7. Kolekcja Harwell-Boeing - [Zasoby elektroniczne] – Tryb dostępu. - URL: http://math.nist.gov/MatrixMarket/data/Harwell-Boeing/ (data dostępu: 15.12.2012)

8. Roland W. Freund, Noel M. Nachtigal. QMR: metoda quasi-minimalnych reszt dla niehermitowskich układów liniowych / Roland W. Freund, Noel M. Nachtigal // Journal Math. - 1991. - nr 60. - P. 315-339.

9.Saad, Y. Metody iteracyjne dla rzadkich układów liniowych / Y. Saad. // SYJAM. - 2003. - 447 s.

Transkrypcja

1 6. Zdegenerowane i źle uwarunkowane SLAE 1 6. Zdegenerowane i źle uwarunkowane SLAE Rozważmy teraz dwa typy SLAE (27) z macierzą kwadratową A o rozmiarze MxM: układ zdegenerowany (z wyznacznikiem zerowym A =0); układ źle uwarunkowany (wyznacznik A nie jest równy zero, ale liczba warunku jest bardzo duża). Pomimo tego, że tego typu układy równań znacznie różnią się od siebie (dla pierwszego nie ma rozwiązania, ale dla drugiego jest tylko jedno), z praktycznego punktu widzenia komputera, istnieje między nimi wiele wspólnego ich. System zdegenerowany to układ opisany macierzą z wyznacznikiem zerowym A = 0 (macierz osobliwa). Ponieważ niektóre równania zawarte w takim układzie są reprezentowane przez liniową kombinację innych równań, to w rzeczywistości sam układ jest niedookreślony. Łatwo zdać sobie sprawę, że w zależności od konkretnego typu wektora prawej strony b istnieje albo nieskończona liczba rozwiązań, albo nie ma ich wcale. Rozważmy pierwszy przypadek, gdy SLAE A x=b z pojedynczą macierzą kwadratową A nie ma jednego rozwiązania. Opcja ta sprowadza się do skonstruowania pseudorozwiązania normalnego (czyli wybrania z nieskończonego zbioru rozwiązań tego, które jest najbliższe pewnemu, np. zerowi, wektorowi). Podajmy przykład takiego problemu (dla układu dwóch równań) A= , b= (37) SLAE (37) ilustruje rys. 19, z którego wynika, że ​​dwa równania definiujące układ definiują dwie równoległe linie na płaszczyźnie (x 1, x 2). Linie nie przecinają się w żadnym punkcie

2 2 6. Zdegenerowane i źle uwarunkowane SLAE w jednym punkcie płaszczyzny współrzędnych, w związku z czym nie ma rozwiązania dla układu. Należy zauważyć, że SLAE, zdefiniowany przez nieosobliwą macierz kwadratową o wymiarach 2x2, definiuje parę przecinających się linii na płaszczyźnie (patrz rysunek poniżej). Warto też powiedzieć, że gdyby układ był spójny, to geometryczną reprezentacją równań byłyby dwie pokrywające się linie opisujące nieskończoną liczbę rozwiązań. Ryż. 19. Graficzne przedstawienie niekompatybilnego SLAE Rys. 20. Wykres przekrojów reszty f(x)= A x b w zależności od x 1 Łatwo się domyślić, że w rozpatrywanym przypadku osobliwym będzie nieskończenie wiele pseudorozwiązań układu (37) minimalizujących resztę A x b, i będą leżeć na trzeciej prostej równoległej do dwóch pokazanych na ryc. 19 i znajduje się pośrodku pomiędzy nimi. Jest to zilustrowane na ryc. 20, który pokazuje kilka przekrojów funkcji resztkowej f(x) = A x b, które wskazują na obecność rodziny minimów o tej samej głębokości. Aby wyznaczyć rozwiązanie unikalne, należy z całego zbioru pseudorozwiązań wybrać to, które je posiada

3 6. Zdegenerowane i źle uwarunkowane SLAE 3 według najmniejszej normy. Zatem w pojedynczym przypadku, aby otrzymać wyróżnione rozwiązanie, konieczne jest numeryczne rozwiązanie wielowymiarowego problemu minimalizacji. Jednak, jak zobaczymy później, bardziej efektywnym sposobem jest użycie regularyzacji lub rozkładów macierzy ortogonalnych (patrz odpowiednio 7 i 10). Przejdźmy teraz do systemów źle uwarunkowanych, tj. SLAE z macierzą A, której wyznacznik nie jest równy zero, ale liczba warunku A -1 A jest duża. Pomimo tego, że źle uwarunkowane systemy posiadają unikalne rozwiązanie, w praktyce często nie ma sensu szukać takiego rozwiązania. Rozważmy właściwości źle uwarunkowanych SLAE, używając dwóch konkretnych przykładów bardzo bliskich źle uwarunkowanych SLAE z tą samą prawą stroną b i nieco innymi macierzami A i B: A= B=, b=, 3 5. (38 ) Pomimo bliskości tych układów, ich dokładne rozwiązania okazują się bardzo odległe od siebie, a mianowicie: y A = , y B = (39) Jeśli pamiętamy obecność szumu, tj. o zawsze występującym błędzie w danych wejściowych staje się jasne, że rozwiązywanie źle uwarunkowanych systemów metodami standardowymi nie ma żadnego sensu. Przypomnijmy, że problemy, w przypadku których małe błędy modelu (macierz A i wektor b) prowadzą do dużych błędów rozwiązania, nazywane są niepoprawnymi. Zatem źle uwarunkowane SLAE są typowym przykładem źle postawionych problemów. Dodatkowo należy zaznaczyć, że dla układu dwóch równań łatwo jest uzyskać rozwiązanie dokładne, natomiast przy rozwiązywaniu wielowymiarowego SLAE (w tym za pomocą algorytmu „dokładnego”

4 4 6. Zdegenerowane i źle uwarunkowane Gaussa SLAE) nawet drobne błędy zaokrągleń, które nieuchronnie kumulują się podczas obliczeń, prowadzą do ogromnych błędów w wynikach. Powstaje pytanie: czy jest sens szukać rozwiązania numerycznego, jeśli z góry wiadomo, że ze względu na niestabilność samego problemu może okazać się ono całkowicie błędne? Aby lepiej zrozumieć przyczynę nieprawidłowości, warto porównać graficzną interpretację dobrze (ryc. 21) i słabo (ryc. 22) uwarunkowanego układu dwóch równań. Rozwiązanie układu ilustruje punkt przecięcia dwóch prostych reprezentujących każde z równań. Ryż. 21. Wykres dobrze kondycjonowanego SLAE Ryc. 22. Wykres źle kondycjonowanego SLAE Z ryc. 22 widać, że linie proste odpowiadające źle uwarunkowanemu SLAE znajdują się blisko siebie (prawie równolegle). Pod tym względem niewielkie błędy w lokalizacji każdej z linii mogą prowadzić do znacznych błędów w lokalizacji punktu ich przecięcia (rozwiązania SLAE), w przeciwieństwie do przypadku układu dobrze uwarunkowanego, gdy małe błędy w nachylenie linii ma niewielki wpływ na położenie ich punktu przecięcia (ryc. 21).

5 6. Zdegenerowane i źle uwarunkowane SLAE 5 Należy zauważyć, że źle kondycjonowana matryca jest również typowa przy rekonstrukcji danych eksperymentalnych podanych przez nadokreślone (niekompatybilne) SLAE (np. w problemach tomograficznych). Aby rozwiązać źle postawione problemy, w szczególności zdegenerowane i źle uwarunkowane SLAE, opracowano bardzo skuteczną metodę zwaną regularyzacją. Polega ona na uwzględnieniu a priori dodatkowych informacji o strukturze rozwiązania, które bardzo często są dostępne w praktycznych przypadkach.

10. Rozkłady QR i SVD: „złe” SLAE 1 10. Rozkłady QR i SVD: „złe” SLAE Wśród rozkładów macierzowych szczególną rolę odgrywają dekompozycje ortogonalne, które mają właściwość zachowania normy wektor. Przypomnijmy

7. Regularyzacja 1 7. Regularyzacja Aby rozwiązać źle postawione problemy, radziecki matematyk Tichonow zaproponował prostą, ale niezwykle skuteczną metodę zwaną regularyzacją, opartą na uwikłaniu

Przykład: ważenie 1 Przykład: ważenie Podajmy jeszcze prostszą interpretację odwrotnego problemu związanego z przetwarzaniem wyników eksperymentu, na przykład ważenia obiektów dwóch typów

Temat Metody numeryczne algebry liniowej - - Temat Metody numeryczne algebry liniowej Klasyfikacja Istnieją cztery główne działy algebry liniowej: Rozwiązywanie układów liniowych równań algebraicznych (SLAE)

UDC 55 Isabekov KA Madanbekova EE YSU nazwany na cześć KTynystanova O PRZYBLIŻONYM ROZWIĄZANIU UKŁADÓW NIEWARUNKOWANYCH LINIOWYCH RÓWNAŃ ALGEBRAICZNYCH W artykule przedstawiono algorytmy dla dwóch metod rozwiązywania złego

Specjalne warsztaty obliczeniowe z badaniami naukowymi Nikolai Matveevich Andrushevsky, Wydział Informatyki Moskiewskiego Uniwersytetu Państwowego Streszczenie Warsztaty opierają się na szczegółowym badaniu metody rozkładu macierzy na wartości osobliwe i jej zastosowaniu

Nadokreślone układy równań liniowych Skalko Jurij Iwanowicz Cybulin Iwan Szewczenko Aleksander Nadokreślone SLAE Przedeterminowane SLAE Rozważmy SLAE Ax = b, ale w przypadku, gdy równań jest więcej,

Układy liniowych równań algebraicznych Pojęcia podstawowe Układ liniowych równań algebraicznych (SLAE) jest układem w postaci a a a, a a a, a a a Można go przedstawić w postaci równania macierzowego

Egzamin Ne LA dla licencjatów z ekonomii w roku akademickim 04-0, Znajdź wektor Ne (6 4; 6 8) i Ne DEMO opcja 0 (x; y) (dla których Ne i x< 0) такой, чтобы система векторов (x ; y) образовывала бы ортогональный

Równanie prostej w przestrzeni 1 Linia jest przecięciem dwóch płaszczyzn. Układ dwóch równań liniowych z trzema niewiadomymi. Linię prostą w przestrzeni można zdefiniować jako przecięcie dwóch płaszczyzn. Pozwalać

WYKŁAD 6 ZADANIA Widmowe. Metody zniżania Na ostatnim wykładzie omawiane były metody iteracyjne typu wariacyjnego. Dla układu Au = f, dla którego A = A wprowadzono funkcjonał Φ(u, u).

11. Redukcja liniowa 1 11. Redukcja liniowa Zakończmy naszą rozmowę o problemach odwrotnych liniowo, przedstawiając inne podejście zwane redukcją. Zasadniczo jest bardzo blisko regularyzacji (w niektórych

01 1. Znajdź rozwiązania ogólne i podstawowe układu równań: x + x + 3x = 26, 2x 12x x = 22, x + 3x + 2x = 20, wybierając x i x jako zmienne podstawowe. Odpowiedź: Jeśli jako podstawowe wybierzemy zmienne

Demo 01 1. Znajdź rozwiązania ogólne i podstawowe układu równań: x + x + 3x = 26, 2x 12x x = 22, x + 3x + 2x = 20, wybierając x i x jako zmienne podstawowe. 2. Znajdź podstawę systemu

Moskiewski Państwowy Uniwersytet Techniczny im. NE Baumana Wydział Nauk Podstawowych Katedra Modelowania Matematycznego ÀÍ Ę asiakov,

UDC 57.9 Igrunova S.V., kandydat nauk socjologicznych, profesor nadzwyczajny, profesor nadzwyczajny Wydziału Systemów Informacyjnych Rosja, Biełgorod Kichigina A.K. Student IV roku Instytutu Technologii Inżynierskich i Nauk Przyrodniczych

6 Metody aproksymacji funkcji. Najlepsze przybliżenie. Metody aproksymacji omówione w ostatnim rozdziale wymagają, aby węzły funkcji siatki ściśle należały do ​​wynikowego interpolanta. Jeśli nie żądasz

ELEMENTY ALGEBRA LINIOWEJ KLASYFIKACJA MACIERZY I DZIAŁAŃ NA NICH Zdefiniowanie macierzy Klasyfikacja macierzy według rozmiaru Czym są macierze zerowe i tożsamościowe? W jakich warunkach macierze uważa się za równe?

) Pojęcie SLAE) Reguła Cramera do rozwiązywania SLAE) Metoda Gaussa 4) Ranga macierzy, twierdzenie Kroneckera-Capelliego 5) Rozwiązywanie SLAE metodą inwersji macierzy, koncepcja warunkowania macierzy) Pojęcie SLAE O. System SLAE

Obliczenia równoległe w tomografii. Metody algebraiczne tomografii komputerowej. Problem tomografii komputerowej w postaci dyskretnej Problem tomografii komputerowej w postaci dyskretnej. W przeciwieństwie

WYKŁAD 2 NUMERYCZNE ROZWIĄZANIE SLAE Z reguły przy rozwiązywaniu większości praktycznych problemów problem rozwiązywania układów liniowych równań algebraicznych (SLAE) występuje w postaci jakiegoś podzadania pomocniczego.

Przykłady podstawowych problemów metody LA Gaussa Niektóre układy równań liniowych Rozwiąż układ równań liniowych metodą Gaussa x 6 y 6 8, 6 x 6 y 6 Rozwiąż układ równań liniowych metodą Gaussa 6

Badania Operacyjne Definicja Operacja to zdarzenie mające na celu osiągnięcie określonego celu, uwzględniające kilka możliwości i zarządzanie nimi Definicja Badania Operacyjne zbiór matematycznych

Wykład 3. 3. Metoda Newtona (styczne. Ustalmy wstępne przybliżenie [,b] i zlinearyzujmy funkcję f(w sąsiedztwie wykorzystując odcinek szeregu Taylora f(= f(+ f ”((-. (5 Zamiast równania (My rozwiązujemy

Równania prostej i płaszczyzny Równanie prostej na płaszczyźnie. Równanie ogólne prostej. Znak równoległości i prostopadłości linii. We współrzędnych kartezjańskich zdefiniowana jest każda linia prosta na płaszczyźnie Oxy

Moskiewski Państwowy Uniwersytet Techniczny nazwany na cześć N.E. Baumana Wydział Nauk Podstawowych Katedra Modelowania Matematycznego A.N. Kasikow,

Przykłady wypełniania prac testowych w trakcie nauczania na odległość Praca testowa 1 (CR-1) Temat 1. Algebra liniowa Zadanie 1 Należy rozwiązać układ równań przedstawiony w zadaniu w postaci Parametry stałe

Moskiewski Państwowy Uniwersytet Techniczny nazwany imieniem. NE Wydział Baumana Katedra Nauk Podstawowych Matematyka Wyższa Geometria Analityczna Moduł 1. Algebra macierzy. Wykład z algebry wektorowej

Bilet. Macierze, działania na nich. Równanie paraboli w kanonicznym układzie współrzędnych. Bilet. Własności operacji na macierzach.Względne położenie prostej i płaszczyzny. Kąt między nimi, warunki równoległości

3 SPIS TREŚCI 1. Cele i zadania dyscypliny 4. Miejsce dyscypliny w strukturze BOP 4 3. Struktura i treść dyscypliny 5 3.1. Struktura dyscypliny 5 3.. Treść dyscypliny 6 4. Wykaz materiałów dydaktycznych i metodycznych

LEKCJE PRAKTYCZNE Lekcja WARUNKI KONIECZNE I WYSTARCZAJĄCE DLA EKStremUM BEZWARUNKOWEGO. Opis problemu Biorąc pod uwagę dwukrotnie różniczkowalną w sposób ciągły funkcję f (), zdefiniowaną na zbiorze X R Wymagane do zbadania

Rozwiązania problemów z algebry na drugi semestr D.V. Gorkovets, F.G. Korablev, V.V. Korableva 1 Liniowe przestrzenie wektorowe Zadanie 1. Czy wektory w R4 są liniowo zależne? za 1 = (4, 5, 2, 6), za 2 = (2, 2, 1,

Federalna Państwowa Edukacyjna Instytucja Budżetowa Wyższego Szkolnictwa Zawodowego „Uniwersytet Finansowy pod Rządem Federacji Rosyjskiej” (Uniwersytet Finansowy) WYDZIAŁ „MATEMATYKI”

Xətti ər Rus) üui ithhn sullrı Pokaż, że wektor;;) ;;) ; ;) utwórz bazę wektora i napisz kombinację liniową wektora If;;) na tych wektorach znajdź X z równania Pokaż, że wektor;)

Twierdzenie Kroneckera-Capelliego. Rozwiązywanie SLAE metodą Gaussa. Ranga matrycy. Rozważmy macierz prostokątną z m wierszami i kolumnami: A. m m m Wybierzmy w tej macierzy dowolne wiersze i kolumny. Elementy

Układy równań liniowych z dwiema zmiennymi Układ równań w postaci nazywany jest układem równań liniowych z dwiema zmiennymi. Rozwiązaniem układu równań z dwiema zmiennymi jest para wartości

ALGEBRA LINIOWA Wykład Linia i płaszczyzna w przestrzeni Treści merytoryczne: Równanie płaszczyzny Wzajemny układ płaszczyzn Równanie wektorowo-parametryczne prostej Równania prostej z dwóch punktów Linia

UNIWERSYTET PAŃSTWOWY W Petersburgu Wydział Matematyki Stosowanej Procesów Sterowania A. P. IVANOV, Y. V. OLEMSKOY PRAKTYKA Z METOD NUMERYCZNYCH MINIMALIZACJA FUNKCJI KWADRATOWEJ Metodyczne

0 g 6 Postępowanie FORA NUMER WARUNKU MATRYCY JAKO WSKAŹNIK STABILNOŚCI PRZY ROZWIĄZYWANIU STOSOWANYCH PROBLEMÓW R Tsey, MM Shumafov Adygea State University, Maikop Numer warunku macierzy

MACIERZE, WYZNACZNIKI, UKŁADY RÓWNAŃ LINIOWYCH Metoda graniczenia mollów w celu znalezienia rzędu macierzy A = m m m minor Minor k rzędu k macierzy A jest dowolną wyznacznikiem k-tego rzędu tej macierzy,

WYKŁAD 4 ITERATYWNE METODY ROZWIĄZANIA SLAE Aby zredukować błąd związany z zaokrąglaniem, skorzystaj z następującego algorytmu. Niech u będzie rozwiązaniem dokładnym układu, u rozwiązaniem numerycznym. Następnie wprowadzimy

1. Układy i macierze liniowe. 1. Zdefiniować mnożenie macierzy. Czy ta operacja jest przemienna? Wyjaśnij odpowiedź. Iloczyn C macierzy A i B definiuje się jako m p m p A B ij = A ik B kj. Operacja nie jest przemienna.

MINISTERSTWO EDUKACJI I NAUKI FEDERACJI ROSYJSKIEJ TOMSK PAŃSTWOWY UNIWERSYTET SYSTEMÓW KONTROLI I ELEKTRONIKI RADIOWEJ (TUSUR) Yu.E. Woskobojnikow A.A. Mitzel NIEPOPRAWNE PROBLEMY MATEMATYCZNE

METODY NUMERYCZNE ALGEBRA LINIOWEGO W rozdziale „Metody numeryczne algebry liniowej” omówiono metody numeryczne rozwiązywania układów liniowych równań algebraicznych (SLAE) oraz metody numeryczne rozwiązywania problemów

GEOMETRIA ANALITYCZNA 3 STREAM Wykładowca P. V. Golubtsov 1.1. Wektory. Lista pytań do pierwszej części egzaminu 1. Sformułuj definicję operacji liniowych na wektorach. Wymień właściwości operacji liniowych

Układy liniowych równań algebraicznych Rozważmy układ m liniowych równań algebraicznych z niewiadomymi b b () m m m bm Układ () nazywa się jednorodnym, jeśli wszystkie jego wolne człony b b b m są równe

4. Układy równań liniowych. Pojęcia podstawowe Równanie nazywamy liniowym, jeśli zawiera niewiadome tylko pierwszego stopnia i nie zawiera iloczynów niewiadomych, tj. jeśli ma postać +++

Algebra liniowa Wykład 7 Wektory Wprowadzenie W matematyce istnieją dwa rodzaje wielkości: skalary i wektory Skalar jest liczbą, a wektor jest intuicyjnie rozumiany jako obiekt, który ma wielkość i kierunek Rachunek wektorowy

Lista pytań na egzamin z metod numerycznych (28.05.2018) 0.1 Całkowanie numeryczne 1. Wymienić metody obliczania całek niewłaściwych. Skonstruuj wzór kwadraturowy, aby obliczyć całkę

Obliczenia równoległe w tomografii Prosta metoda iteracyjna. Metoda najbardziej stromego zejścia. Metoda ART. Metoda SIRT. W prostej metodzie iteracyjnej współczynniki relaksacji τ k i macierze H k nie zależą od liczby

Wprowadzenie do algebry macierzy liniowych. Definicja. Tablicę m n liczb w postaci m m n n mn składającą się z m wierszy i n kolumn nazywamy macierzą. Elementy macierzy numeruje się podobnie jak elementy wyznacznika

WYKŁAD 7 INTERPOLACJA Na ostatnim wykładzie rozważano problem rozwiązania układu nadokreślonego. Układ taki ma postać: a 11 x 1 + a 1 x + + a 1 x = f 1, ( a 1 x 1 + a x + + a x = f, ( a 1 x 1 + a x

ZADANIA TEORETYCZNE I. MACIERZE, WYZNACZNIKI 1) Podaj definicję macierzy. Co to są macierze zerowe i macierze tożsamościowe? W jakich warunkach macierze uważa się za równe? Jak przeprowadzana jest operacja transpozycji? Gdy

Wykład 7 SPROWADZANIE KRZYWEJ DRUGIEGO RZĘDU DO POSTACI KANONICZNEJ. Transformacja baz i współrzędnych na płaszczyźnie Niech na płaszczyźnie dane będą dwa prostokątne kartezjańskie układy współrzędnych o wspólnym początku:

Algebra liniowa Moduł 1. Przestrzenie liniowe i euklidesowe. Operatory liniowe w przestrzeni liniowej Wykład 1.4 Streszczenie Wektory własne i wartości własne operatora liniowego, ich własności.

UDC. SYNTEZA REKURSywnyCH FILTRÓW CYFROWYCH WEDŁUG CHARAKTERYSTYKI IMPULSOWEJ OKREŚLONEJ PRZEZ ELEMENTARNĄ FUNKCJĘ MATEMATYCZNĄ Nikitin D.A., Chanov V.Kh. Wprowadzenie We współczesnym arsenale metod syntezy rekurencyjnej

Rozdział 8 Funkcje i wykresy Zmienne i zależności pomiędzy nimi. Dwie wielkości nazywane są wprost proporcjonalnymi, jeśli ich stosunek jest stały, to znaczy jeśli =, gdzie jest stałą liczbą, która nie zmienia się wraz ze zmianami

Metoda Gaussa (metoda eliminowania niewiadomych) Dwa układy nazywamy równoważnymi (równoważnymi), jeśli ich rozwiązania są zbieżne. Do układu równoważnego można przejść stosując przekształcenia elementarne

Wiadomo, jakie trudności wiążą się z rozwiązywaniem tzw. układów źle uwarunkowanych liniowych równań algebraicznych: niewielkim zmianom po prawej stronie takich układów mogą odpowiadać duże (poza akceptowalne granice) zmiany rozwiązania.

Rozważmy układ równań

Аz=ty, (3; 2,1)

Gdzie A -- macierz z elementami a ij , A=(a ij ), z -- żądany wektor o współrzędnych z j , z=(z jot ), I -- znany wektor ze współrzędnymi I I , ty= (u ja ), ja, j =1, 2, ..., P. Nazywa się system (3; 2,1). zdegenerowany, jeśli wyznacznik układu wynosi zero, detA = 0. W tym przypadku macierz A ma zerowe wartości własne. W przypadku źle uwarunkowanych układów tego typu matryca A ma wartości własne bliskie zeru.

Jeżeli obliczenia wykonuje się ze skończoną dokładnością, to w niektórych przypadkach nie da się stwierdzić, czy dany układ równań jest zdegenerowany, czy źle uwarunkowany. Zatem systemy źle uwarunkowane i zdegenerowane mogą być nie do odróżnienia w ramach danej precyzji. Oczywiście taka sytuacja ma miejsce w przypadkach, gdy matrix A ma wartości własne całkiem bliskie zeru.

W problemach praktycznych często stosuje się prawą stronę I i elementy macierzy A, tj. współczynniki układu (3; 2,1) są znane w przybliżeniu. W takich przypadkach zamiast systemu (3;2,1) mamy do czynienia z jakimś innym układem Az= I tak, że ||A-A||<=h, ||u-u||<=--d, где смысл норм обычно определяется характером задачи. Имея вместо матрицы A macierzy A, tym bardziej nie możemy jednoznacznie ocenić degeneracji lub braku degeneracji systemu (3; 2.1).

W takich przypadkach chodzi o dokładny system Аz=ty, którego rozwiązanie należy wyznaczyć, wiemy to tylko dla macierzy A i prawa strona I nierówności ||A-A||<=h, ||u-u||<=--d. Но систем с такими исходными данными (Ręka) nieskończenie wiele i na znanym nam poziomie błędu są nie do odróżnienia. Ponieważ zamiast systemu dokładnego (3; 2.1) mamy system przybliżony Аz= i, wówczas możemy mówić jedynie o znalezieniu przybliżonego rozwiązania. Ale przybliżony system Az=ty może być nierozpuszczalny. Nasuwa się pytanie:

co należy rozumieć jako przybliżone rozwiązanie układu (3; 2.1) w opisywanej sytuacji?

Wśród „możliwych systemów dokładnych” mogą znajdować się również systemy zdegenerowane. Jeśli są rozwiązywalne, to mają nieskończenie wiele rozwiązań. Które z nich powinniśmy mówić o znalezieniu przybliżonym?

Zatem w dużej liczbie przypadków musimy rozpatrywać całą klasę układów równań, które są od siebie nieodróżnialne (w ramach danego poziomu błędu), wśród których mogą znajdować się zarówno układy zdegenerowane, jak i nierozwiązywalne. Metody konstruowania przybliżonych rozwiązań układów tej klasy muszą być takie same i ogólne. Rozwiązania te muszą być odporne na niewielkie zmiany danych wyjściowych (3; 2.1).

Konstrukcja takich metod opiera się na idei „selekcji”. Selekcji można dokonać za pomocą specjalnych, wcześniej określonych funkcjonałów W[ z ] zawartych w opisie problemu.

Nieujemny funkcjonał W[ z] zdefiniowany na wszędzie gęstym podzbiorze F 1 z F w F nazywa się stabilizacja funkcjonalności, Jeśli:

• a) element z T należy do swojej dziedziny definicji;
• b) dla dowolnej liczby d>0 zbiór F 1,d elementy z z F 1 dla których
• W[z]

Rozważmy więc dowolny układ liniowych równań algebraicznych (w skrócie SLAE)

Az = ty, (3; 2,2)

w którym z i u są wektorami, z=(z 1, z 2, ...,z n)-OR n, I=(u 1, u 2 , ... ,u n)--LUB m , A-- macierz z elementami a ij , A= (a ij ), gdzie j =1, 2, ..., n; ja= 1, 2, ..., T, i numer P nie musi być równa liczbie T.

Układ ten może być jednoznacznie rozwiązywalny, zdegenerowany (i mieć nieskończenie wiele rozwiązań) i nierozwiązalny.

Pseudo-rozwiązanie układ (3; 2,2) nazywany jest wektorem z minimalizującym rozbieżność || Az - ty || na całej przestrzeni Rn. Układ (3; 2,2) może mieć więcej niż jedno pseudorozwiązanie. Niech F A będzie zbiorem wszystkich jego pseudorozwiązań i niech z 1 będzie jakimś ustalonym wektorem Rn, zwykle określane przez określenie problemu.

Normalna względem wektora z 1 rozwiązanie układu (3;2,2) będziemy nazywać pseudorozwiązaniem z 0 z normą minimalną || z - z 1 ||, czyli takie, że

|| z 0 - z 1 || =

Tutaj. W dalszej części, dla uproszczenia zapisu, założymy, że z 1 = 0, a rozwiązanie normalne względem wektora z 1 = 0 będzie po prostu nazywane normalne rozwiązanie.

Dla dowolnego układu postaci (3; 2,2) istnieje rozwiązanie normalne i jest ono unikalne.

Uwaga 1. Rozwiązanie normalne z° układu (3;2,2) można również zdefiniować jako pseudorozwiązanie minimalizujące zadaną dodatnio określoną postać kwadratową względem współrzędnych wektora z--z 1 . Wszystkie wyniki zaprezentowane poniżej pozostają aktualne.

Uwaga 2. Niech ranga macierzy A układ zdegenerowany (3; 2,1) jest równy r < n i z r+1 ,z r+2 , … , z n - baza przestrzeni liniowej N A , składający się z elementów z dla których AZ=0, NA = ( z; AZ= 0). Rozwiązanie z° układu (3; 2,1), spełniające warunki n--r ortogonalności

(z 0 - z 1 , z S)= 0, S= r + 1, r + 2, .. ,n, (3; 2,3)

jest określony jednoznacznie i pokrywa się z rozwiązaniem normalnym.

Łatwo zauważyć, że problem znalezienia normalnego rozwiązania układu (3; 2,2) jest źle postawiony. A właściwie niech A -- macierz symetryczna. Jeśli nie jest zdegenerowany, to poprzez transformację ortogonalną

z = Vz*, u = Vu*

jej można sprowadzić do postaci diagonalnej i przekształcony układ będzie miał postać

l i z ja *=u ja * , i= 1, 2,. .., P,

gdzie l ja są wartościami własnymi macierzy A.

Jeśli macierz symetryczna A -- jest niezdegenerowany i ma stopień r, wówczas n - r jego wartości własnych jest równych zero. Pozwalać

l i №0 dla i=1, 2, ..., r;

l i =0 dla i=r+1,r+2, …, n.

Zakładamy, że układ (3; 2,2) jest rozwiązywalny. W tym przypadku u i *= 0 dla i =r + 1, ..., n.

Niech „dane początkowe” systemu (A I I) określony z błędem, tj. zamiast A I I podano ich przybliżenia A I ty:

|| A - A ||<=h, ||u - u||<=d . При этом

Niech ja -- wartości własne macierzy A. Wiadomo, że w sposób ciągły zależą one od A w normie (3; 2,4). W konsekwencji wartości własne l r+1 , l r+2 , …,l n może być dowolnie mały dla wystarczająco małego h .

Jeśli nie są równe zero, to

Zatem w obrębie wystarczająco małego błędu wystąpią zakłócenia w systemie A I I, dla których niektóre z i * przyjmą dowolne z góry określone wartości. Oznacza to, że problem znalezienia normalnego rozwiązania układu (3; 2,2) jest niestabilny.

Poniżej znajduje się opis metody znajdowania rozwiązania normalnego układu (3; 2.2), od stabilnych do małych (w normie (3; 2.4)) zaburzeń prawej strony I, w oparciu o metodę regularyzacji.