Методичка (864359), страница 2

Просмтор этого файла доступен только зарегистрированным пользователям. Но у нас супер быстрая регистрация: достаточно только электронной почты!

Текст из файла (страница 2)

+ λ mp cm , km em, km .10Видно, что при больших значениях p доминирует вклад от базисных векторов, отвечающих наибольшему по модулю собственному значению λ1. Отсюда получаем алгоритм степенного метода.Строим последовательность векторов:x1 =Ax 0x0, x2 =Ax1x1, ..., x p =Ax p −1x p −1.Критерий окончания процесса x p − sign( xip xip −1 ) x p −1 < ε (выражение sign( xip xip −1 )) следует учитывать, поскольку собственноезначение матрицы может быть отрицательным), где точность ε задана (например, ε = 0,000 001). Тогда λ1 ≈ xip xip −1 x p −1 , гдеx p = ( x1p , x2p ,..., xnp ) .

Для правильной работы алгоритма важно, что-бы вектор x 0 содержал ненулевую проекцию на собственное подпространство, отвечающее собственному значению λ1.Нахождение меры обусловленностисимметричной матрицы A степенным методомЕсли А — симметричная матрица, λ1, λ2, λ3, …, λm — ее собственные числа, то евклидова норма A = max λ i .i =1,..., mС помощью степенного метода можно найти и норму A−1 .Для этого мы должны построить последовательностьx1 =A−1 x 0x0, x2 =A−1 x1x1, ..., x p =A−1 x p −1x p −1,илиAx1 =x0x0, Ax 2 =x1x1, ..., Ax p =x p −1x p −1.То есть на каждом шаге для нахождения значения x i решаемсоответствующую систему линейных алгебраических уравненийAx i = x i −1 x i−1 .Критерийокончанияпроцесса11x p − sign( xip xip −1 ) x p −1 < ε , где точность ε задана (в лабораторныхработахε = 0,000 001).Тогдаλ1 ≈ xip xip −1 x p −1иA−1 = λ1 .Мера обусловленности матрицы A равна ν( A) = A ⋅ A−1 .1.2.

Решение систем линейных алгебраических уравненийметодом ГауссаРассмотрим систему линейных алгебраических уравнений(СЛАУ) видаAx = b ,где⎛ a11⎜a21A=⎜⎜ ...⎜⎝ an1a12a22...an 2... a1n ⎞⎟... a2 n ⎟;... ... ⎟⎟... ann ⎠⎛ a1,n +1 ⎞⎜⎟a2,n +1 ⎟⎜b=.⎜ ... ⎟⎜⎜⎟⎟⎝ an ,n +1 ⎠Перепишем ее в развернутом виде:a11 x1 + a12 x2 + ... + a1n xn = a1, n +1 ;a21 x1 + a22 x2 + ... + a2 n xn = a2, n +1 ;...an1 x1 + an 2 x2 + ... + ann xn = an , n +1 .(1.2.1)Прямой ход метода ГауссаПредположив, что a11 ≠ 0, разделим первое уравнение системы(1.2.1) на a11. Получим12nx1 + ∑ a11 j x j = a1,1 n+1.(1.2.2)j =2Из каждого из оставшихся уравнений в (1.2.1) (i = 2, 3, …, n)вычтем уравнение (1.2.2), умноженное на соответствующий коэффициент ai1.

Получимn∑aj=21ijx j = a1j ,n +1 ,i = 2, 3, …, n.(1.2.3)Предположив, что a122 ≠ 0, разделим первое уравнение в (1.2.3)на a122 :nx2 + ∑ a22 j x j = a2,2 n+1 .(1.2.4)j =3Из каждого из оставшихся уравнений в (1.2.3) (i = 3, 4, …, n) вычтем уравнение (1.2.4), умноженное на соответствующий коэффициент ai12 . Получимn∑a x2ijj =3j= ai2,n+1 ,i = 3, 4, …, n.(1.2.5)В результате придем к системеxi +n∑a xiijj =i +1j= aii,n+1 ,i = 1, 2, …, n.(1.2.6)Прямой ход метода Гаусса завершен.Обратный ход метода ГауссаИз формулы (1.2.6) следуетxi = aii , n +1−n∑a xj = i +1iijj,i = n, n – 1, n – 2, …, 1.(1.2.7)Количество арифметических операций при использовании методаГаусса составляет порядка const n3.13Для того чтобы повысить точность вычислений и избежатьвозможного деления на нуль (см. выше: «В предположении, что a11≠ 0…»), используют метод Гаусса с выбором главного элемента.Метод Гаусса с выбором главного элементаПусть на k-м шаге (при k = 0 — исходная система уравнений)получена система уравнений:xi +n∑aj = k +1kijn∑a xj =i +1iijj= aii,n+1 ,x j = aik,n+1 ,i = 1, 2, …, k;i= k + 1, k + 2, …, n.Пустьalk,k +1 = max aik,k +1 , i = k + 1, …, n.Переставляем местами l-ю и (k + 1)-ю строки.

Если при этомalk,k +1 = 0, то это означает, что определитель матрицы А равен нулю и система уравнений либо не имеет решений, либо имеет ихбесконечно много (теорема Кронекера — Капелли).Далее продолжаем применять стандартный метод Гаусса, покане спустимся на ступеньку ниже, после чего повторим процедуру.Пример. Рассмотрим систему уравнений⎛1⎜⎜3⎜8⎜⎝64 ⎞ ⎛ x1 ⎞ ⎛ 22 ⎞⎟ ⎜ ⎟ ⎜ ⎟7 ⎟ ⎜ x2 ⎟ ⎜ 38 ⎟⋅=.2 0 −2 ⎟ ⎜ x3 ⎟ ⎜ 16 ⎟⎟ ⎜ ⎟ ⎜ ⎟6 6 9 ⎠ ⎝ x4 ⎠ ⎝ 60 ⎠2 35 1Поделим первую строку на a11 = 1 и вычтем получившуюсястроку из второй, третьей и четвертой строк, домножив первуюстроку на a21 = 3, a31 = 8, a41 = 6 соответственно. В результатеполучим1434 ⎞ ⎛ x1 ⎞ ⎛ 22 ⎞⎛1 2⎜⎟ ⎜ ⎟ ⎜⎟⎜ 0 −1 −8 −5 ⎟ ⋅ ⎜ x2 ⎟ = ⎜ −28 ⎟ .⎜ 0 −14 −24 −34 ⎟ ⎜ x3 ⎟ ⎜ −160 ⎟⎜⎟ ⎜ ⎟ ⎜⎟⎝ 0 −6 −12 −15 ⎠ ⎝ x4 ⎠ ⎝ −72 ⎠Поделим вторую строку на a122 = −1, вычтем получившуюся строкуиз третьей и четвертой строк, домножив вторую строку на11a 32 = −14, a 42 = −6 соответственно. В результате получим⎛1⎜⎜0⎜0⎜⎝04 ⎞ ⎛ x1 ⎞ ⎛ 22 ⎞⎟ ⎜ ⎟ ⎜⎟5 ⎟ ⎜ x2 ⎟ ⎜ 28 ⎟⋅=.0 88 36 ⎟ ⎜ x3 ⎟ ⎜ 232 ⎟⎟ ⎜ ⎟ ⎜⎟0 36 15 ⎠ ⎝ x4 ⎠ ⎝ 96 ⎠21382= 88 и вычитаем ее из четвертой строДелим третью строку на a 33ки, домножив третью строку на a 243 = 36.

Будем иметь⎛1⎜⎜0⎜0⎜⎝0⎞ ⎛ x1 ⎞ ⎛ 22 ⎞⎟ ⎜ ⎟ ⎜⎟⎟ ⋅ ⎜ x2 ⎟ = ⎜ 28 ⎟ .0 1 9 / 22 ⎟ ⎜ x3 ⎟ ⎜ 29 /11 ⎟⎟ ⎜ ⎟ ⎜⎟0 0 −3 /11⎠ ⎝ x4 ⎠ ⎝ −12 /11⎠2 31 845Находимx4 =−12 ⎛ −3 ⎞: ⎜ ⎟ = 4;11 ⎝ 11 ⎠x3 =299− 4⋅= 1;1122x2 = 28 − (8 ⋅ 1 + 5 ⋅ 4) = 28 − 28 = 0;x1 = 22 − (2 ⋅ 0 + 3 ⋅ 1 + 4 ⋅ 4) = 22 − 19 = 3.15Задание к лабораторной работе«Метод Гаусса с выбором главного элемента»1.

Решить СЛАУ аналитически методом Гаусса с выбором главного элемента (табл. 1.2.1 или 1.2.2 по указанию преподавателя).2. Написать программу решения СЛАУ методом Гаусса с выбором главного элемента. Решить с ее помощью СЛАУ.3. Оформить отчет о лабораторной работе:а) теоретическая часть;б) аналитическое решение системы;в) текст программы;г) результаты решения СЛАУ.Таблица 1.2.1Варианты (1–30) задания для решения СЛАУ Ax = bс четырьмя неизвестными в виде ( A | b ) методом Гаусса121 –2 0–2 0 4–3 –5 44 4 –1–3 | –19–4 | –221 | –230 | 21424–3–51 1 –2 | 53 3 –2 | 31 –5 –3 | 71 1 0 | 115768911–5 1 4 4 | 280 –5 –1 1 | –7–2 2 4 2 | 82 –5 2 –3 | –45–2 0 –1 –1 | 5–2 –1 4 4 | –333 –1 –3 3 | –34 4 –1 –4 | 351 3 2 –1 | –11–1 –5 –5 –3 | 94 0 0 0 | –12–1 –4 –4 1 | 18–3 4 –5 4 | 72 –1 –2 –1 | 64 0 0 –4 | 12–3 –3 –3 –1 | –110–1 0 –2 –4 | –120 –1 3 –1 | 2–3 1 –3 –1 | –23 –3 0 2 | 6–2 –2 –2 –3 | 250 0 –1 –2 | 3–4 –3 –4 –4 | 48–3 –4 –2 –2 | 39–1 –2 3 4 | –13–5 2 4 –2 | –144 3 –2 –1 | 21 –2 –1 –3 | 23163–2 –1 –2 –3 | –7–3 4 2 –4 | –46–4 –2 –2 –2 | –8–3 4 0 2 | –2212–5 4 4 2 | –27–4 –4 –1 –4 | 163 2 –1 1 | 41 3 –2 2 | 22 0 1 1 | –15–2 0 –3 –4 | 31–3 4 1 –1 | –11–5 –3 1 –2 | 34Окончание табл.

1.2.113143 –5–3 14 –42 0–3 –2 –4 3 | 38–2 –4 –5 –5 | 100 2 2 –4 | –26–5 4 4 4 | 1616152 4 | 310 1 | –20 –5 | –34 –4 | 217184 –3 4 –4 | –6–2 –4 0 –5 | 103 –3 0 3 | –24–5 2 –3 3 | 12–1 –1 –1 –1 | 4–4 –5 –1 3 | –4–2 1 1 4 | –280 –4 –1 –3 | 311920–2 –3 03 –4 –3–4 –3 –42 2 –52123242627294 –3 2 –1 | –41 3 4 1| 5–4 0 –1 4 | –1–1 2 1 –4 | 82 0 3 0 | –8–4 3 –2 4 | –3–3 –2 –3 –5 | 15–1 2 2 –2 | 2–2 1 1 3 | –7–4 –3 0 –4 | 21–5 –4 –5 –1 | 481 –3 4 –3 | –101 3 –2 –5 | –110 –1 –1 3 | –1–2 –3 –3 2 | –44 –2 –2 –5 | –2528–1 –5 3 –3 | –300 4 –4 2 | 280 –4 –2 –3 | –18–1 –5 –4 0 | –101 –2 –5 4 | –250 2 –3 1 | –50 0 –3 0 | –34 2 1 4 | –212 –1 –3 –5 | 204 –4 3 1 | 35–5 4 –3 4 | –531 –3 2 0 | 22251 –5 –4 –2 | –24–4 –1 –3 2 | –15–1 0 0 –5 | 27–2 –1 1 –4 | 230 3 –3 –5 | –31 –5 –5 4 | –1–3 –5 1 1 | 16–2 0 –4 2 | –162| 84 | –103| 63 | –5220 –1 4 –4 | –201 3 –1 1 | 15–3 4 –3 –3 | 37–4 1 –3 1 | 224 –4 –1 3 | 143 –1 –1 –1 | 10–1 2 –2 –5 | 24 3 0 1 | –14300 2 4 1 | –4–1 –4 –4 0 | 203 –3 4 –4 | –1–2 –4 –3 –2 | 21–1 –5 2 –1 | 343 4 –1 –1 | –364 0 –2 1 | –21–5 0 3 4 | 3317Таблица 1.2.2Варианты заданий (1–30) для решения СЛАУ Ax = bс пятью неизвестными в виде ( A | b ) методом Гаусса121 –3 1–4 0 2–2 –4 –2–4 –3 –11 4 31 –5 –1 –5 –5 | –170 1 –1 –5 3 | –22–3 4 –3 –3 –3 | 22–3 –2 0 4 –5 | 393 –4 4 4 –3 | –934–2 4 1 3 –1 | 282 –5 4 –2 –1 | –173 –2 4 2 4 | –28–1 2 2 1 4 | –3–4 –5 –1 4 –5 | 240 –5 1 –5 0 | 271 –3 1 1 –4 | –102 3 –5 –3 4 | 41–4 –5 1 4 3 | –241 –5 1 –5 –4 | 2256–4 –2 1–3 2 3–2 0 –4–4 3 –52 2 0–5243–24 –2 4–4 3 03 3 21 –2 –2–2 –2 –3–1 | –17–1 | 12–3 | –5–2 | –20–5 | –1571–1–4–1–1–3 | –13–3 | 150 | –43 | –9–3 | –1280 –3 –2 –2 0 | 41 –4 0 –4 –5 | –142 2 1 4 –4 | –132 –3 –1 –1 1 | –14 –5 –3 –3 4 | –1–1 4 3 1 4 | 29–1 –3 3 –5 3 | 48–1 –3 –4 2 –2 | –352 0 0 1 4| 72 3 –2 4 0 | –299102–3–4–2–5180 –5 | 224 –1 | 352 1 | –34 –4 | 383 –5 | 444–53–5–3–2–324–3–1 –4 | –31–2 3 | 23 2 | 280 3 | 342 4 | 1924330–1–1–1012–2–34–5–20–3–23–1 | 10–5 | –101| 1– 4 | 17–5 | –26Продолжение табл.

1.2.211124 –1 4 –5 3 | –52 –4 –3 2 0 | –103 3 3 2 0 | –10–5 –5 –5 –2 –5 | 93 3 –3 –3 –4 | 813–5 –3 –3 –5 4 | –54–4 3 –3 4 –1 | –131 –3 0 –2 –2 | –3–5 –1 –1 –3 –3 | –24–1 2 0 –5 –1 | –1142 –3 1 –4 –1 | 252 4 –3 –5 2 | 322 0 –2 –3 3 | 30–3 –4 –1 –1 4 | 234 –2 1 –3 –4 | 1615–3 4 4 2 3 | 143 2 0 –1 –5 | –274 –2 –2 –1 –1 | –144 1 1 –1 1 | –154 4 –4 –1 2 | –4916–4 –1–3 –2–2 –54 –44 –32 0 –5 –2 4 | 430 0 –4 –1 4 | 28–5 –3 –4 –3 –4 | 160 2 1 –2 –3 | –23 4 1 –3 4 | 163 0 –4 | –263 –4 3 | 121 –3 4 | 250 4 0 | –41 –4 –1 | 281718–3 –3 –4 –4 0 | –34–2 –2 2 –5 –3 | –12–1 –5 –4 –5 –2 | –46–1 –3 2 –3 –1 | –14–2 4 3 1 –2 | 374 1 4 –3 4 | 22–3 1 –5 –2 –5 | –160 –5 0 –1 4 | 101 –2 –2 –2 –4 | –201 –1 2 3 –1 | –919203 –5–3 –54 0–2 23 21 –5 –1 2 0 | –13–5 0 –1 –1 0 | 4–1 1 –4 –4 –2 | –4–2 0 –5 –3 1 | –6–4 1 3 1 –4 | 82 –4 –4 | –331 –4 –1 | –162 4 4 | –164 3 –1 | 100 –2 1 | –42122– 4 1 0 1 –1 | 243 –3 –3 2 –3 | 54 4 –3 3 1 | 113 4 1 –5 –5 | –17–1 –5 1 4 –4 | 15–1 –5 –1 –5 –4 | –14–3 2 2 –5 –3 | 243 –2 –2 3 –1 | –160 2 0 4 3| 73 –1 3 2 –3 | –319Окончание табл.

1.2.223240 –2 –1 0 4 | 251 3 –3 –1 0 | –191 1 1 –2 3 | 3–5 2 1 –5 –2 | –52–3 2 1 2 –4 | –264 –1 –3 3 –5 | –23–2 –5 2 –5 –3 | 342 4 3 2 –2 | –313 4 3 –2 4 | 0–2 –4 2 –1 2 | 212526–3 –2 –2 1 –5 | –11–5 0 2 –4 2 | –9–4 1 –1 1 –2 | –11–4 2 0 3 –1 | –4–4 3 0 –5 –2 | –343 1 –4 –2 –5 | 00 3 –2 1 1 | 84 –2 –2 –4 –1 | –174 –3 1 1 –1 | –174 4 –3 3 –5 | 727280 –2 –2 –3 –2 | 160 3 –2 4 3 | –323 –2 4 0 3 | 3–2 –4 0 1 4 | –364 –3 –4 –2 –3 | 281 3 4 –1 –4 | 283 4 –5 –5 –3 | –163 –3 4 0 –1 | 36–2 –5 3 –2 –2 | 314 1 0 1 –3 | 2129303 –1 2 3 0 | 34–4 –1 –2 3 1 | –7–3 –4 2 2 4 | 24–3 –1 4 0 – 4 | –6–1 –1 –2 –5 1 | –27–3 0 –1 –5 –5 | 173 –3 0 –4 –2 | –7–5 3 –5 –2 –3 | 28–3 –1 2 4 1 | 103 –5 –3 –3 –3 | 11.3. Решение систем линейных алгебраических уравненийс помощью LU-разложенияРассмотрим систему уравнений Ax = f .

Характеристики

Список файлов книги