Пусть требуется решить СЛАУ Ax=b с симметрической положительно определенной матрицей A Матрица A приводится к виду A=LLT где

^ Пусть требуется решить СЛАУ Ax=b с симметрической положительно определенной матрицей A Матрица A приводится к виду A=LLT где
L = при

Найдем элементы матрицы L Для этого вычислим элементы матрицы LLT и приравняем Пусть требуется решить СЛАУ Ax=b с симметрической положительно определенной матрицей A Матрица A приводится к виду A=LLT где их подходящим элементам A В итоге получим систему уравнений




Решая эту систему поочередно находим



После того как матрица L будет найдена заменим начальную систему 2-мя эквивалентными ей системами с треугольными матрицами LTy Пусть требуется решить СЛАУ Ax=b с симметрической положительно определенной матрицей A Матрица A приводится к виду A=LLT где=b, Lx=y. Отсюда можно поочередно отыскать



^ Способ прогонки
Это обычной и действенный метод решения СЛАУ с трехдиагональными матрицами:

(6)

Выведем расчетные формулы Из первого уравнения системы (6) получим

 где  

Подставим выражение для во 2-ое уравнение Пусть требуется решить СЛАУ Ax=b с симметрической положительно определенной матрицей A Матрица A приводится к виду A=LLT где системы (6) и получим



Преобразуем это уравнение к виду

 где  

Подставляем последнее выражение в третье уравнение и тд На -м шаге этого процесса () уравнение системы преобразуется к виду

 (7)

где  

На -м шаге подстановка в последнее Пусть требуется решить СЛАУ Ax=b с симметрической положительно определенной матрицей A Матрица A приводится к виду A=LLT где уравнение выражения приведет к уравнению  Отсюда  Значения других неведомых для рассчитываются по формуле (7)

Метод способа прогонки состоит из 2-ух шагов Прямой ход (ровная прогонка) состоит в вычислении прогоночных коэффициентов и  При коэффициенты Пусть требуется решить СЛАУ Ax=b с симметрической положительно определенной матрицей A Матрица A приводится к виду A=LLT где вычисляют по формулам:    а при - по рекуррентным формулам:

  

При ровная прогонка заканчивается вычислением

 

Оборотный ход (оборотная прогонка) дает значения неведомых Поначалу считают  Потом значения других неведомых вычисляют по формуле  

Способ вращений
Прямой ход Пусть требуется решить СЛАУ Ax=b с симметрической положительно определенной матрицей A Матрица A приводится к виду A=LLT где способа На первом шаге исключают из всех уравнений СЛАУ (1) не считая первого Для этого вычисляют   имеющие характеристики  

Потом 1-ое уравнение системы подменяют линейной композицией первого и второго уравнений с коэффициентами Пусть требуется решить СЛАУ Ax=b с симметрической положительно определенной матрицей A Матрица A приводится к виду A=LLT где и  а 2-ое уравнение – аналогичной линейной композицией с коэффициентами и  В итоге получаем систему

(8)

в какой      Было 

Если в начальной системе  то считают  

Выполненное преобразование эквивалентно повороту вектора x вокруг оси на угол Пусть требуется решить СЛАУ Ax=b с симметрической положительно определенной матрицей A Матрица A приводится к виду A=LLT где таковой что  

Для исключения из третьего уравнения вычисляют

 

при этом  

Потом 1-ое уравнение системы (8) подменяют линейной композицией первого и третьего уравнений с коэффициентами и  а третье уравнение – аналогичной композицией с коэффициентами и 

Таким Пусть требуется решить СЛАУ Ax=b с симметрической положительно определенной матрицей A Матрица A приводится к виду A=LLT где же образом исключают из уравнений с номерами  В итоге первого шага (состоит из малых шагов) система приводится к виду

(9)

На втором шаге способа вращений состоящем из малых шагов из уравнений системы Пусть требуется решить СЛАУ Ax=b с симметрической положительно определенной матрицей A Матрица A приводится к виду A=LLT где (9) с номерами исключают  Для этого каждое -е уравнение сочетают со вторым уравнением В итоге приходят к системе:



После окончания -го шага система воспримет вид



Оборотный ход способа вращений – как в способе Гаусса

^ Итерационные способы решений СЛАУ Пусть требуется решить СЛАУ Ax=b с симметрической положительно определенной матрицей A Матрица A приводится к виду A=LLT где
Для систем средней размерности почаще употребляют прямые способы Итерационные способы используют для решения задач большой размерности когда внедрение прямых затруднено из-за необходимости выполнения чрезвычайно огромного числа арифметических операций Пусть требуется решить СЛАУ Ax=b с симметрической положительно определенной матрицей A Матрица A приводится к виду A=LLT где Огромные системы уравнений обычно бывают разреженными Способы исключения приводят к тому что огромное число нулевых частей преобразуются в ненулевые и матрица теряет свойство разреженности А в процессе итерационного процесса матрица не изменяется и Пусть требуется решить СЛАУ Ax=b с симметрической положительно определенной матрицей A Матрица A приводится к виду A=LLT где остается разреженной Большая эффективность итерационных способов по сопоставлению с прямыми способами связана с возможностью существенного использования разреженных матриц


^ Способ обычный итерации (способ Якоби)

СЛАУ Ax=b нужно за ранее конвертировать к виду x=Bx Пусть требуется решить СЛАУ Ax=b с симметрической положительно определенной матрицей A Матрица A приводится к виду A=LLT где+c где B – квадратная матрица с элементами  c – вектор-столбец с  Для приведения системы (1) к виду комфортному для итераций исключим неведомые из уравнений последующим образом:



(10)

На главной диагонали матрицы B находятся нулевые Пусть требуется решить СЛАУ Ax=b с симметрической положительно определенной матрицей A Матрица A приводится к виду A=LLT где элементы а другие  выражаются по формулам:   

Сущность способа Якоби состоит в последующем Выберем изначальное приближение x(0)=и подставив его в правую часть системы (10) найдем 1-ое приближение x(1)=Bx(0)+c Продолжая процесс дальше Пусть требуется решить СЛАУ Ax=b с симметрической положительно определенной матрицей A Матрица A приводится к виду A=LLT где получим последовательность x(0) x(1) … x(k)… приближений вычисляемых по формуле x(k+1)=Bx(k)+c k=0, 1, 2, … либо в развернутом виде:





Способ обычной итерации сходится при условии диагонального доминирования:




^ Способ Зейделя (способ Гаусса Пусть требуется решить СЛАУ Ax=b с симметрической положительно определенной матрицей A Матрица A приводится к виду A=LLT где-Зейделя процесс Либмана способ поочередных замещений)

На k+1-й итерации составляющие приближения x(k+1) рассчитываются по формулам:




Способ Якоби нацелен на системы с матрицами близкими к диагональным а способ Пусть требуется решить СЛАУ Ax=b с симметрической положительно определенной матрицей A Матрица A приводится к виду A=LLT где Зейделя – на системы с матрицами близкими к нижним треугольным

^ Способ релаксации
Способ поочередной верхней релаксации является одним из более действенных и обширно применяемых итерационных способов для решения СЛАУ с симметрическими положительно определенными Пусть требуется решить СЛАУ Ax=b с симметрической положительно определенной матрицей A Матрица A приводится к виду A=LLT где матрицами

После вычисления -й составляющие -го приближения по способу Гаусса-Зейделя

создают дополнительное смещение этой составляющие на величину  где - параметр релаксации Тогда



При способ релаксации совпадает с способом Гаусса-Зейделя при - именуют способом поочередной верхней Пусть требуется решить СЛАУ Ax=b с симметрической положительно определенной матрицей A Матрица A приводится к виду A=LLT где релаксации а при - нижней Но нередко для всех - способом поочередной верхней релаксации

Если СЛАУ имеет симметрическую положительно определенную матрицу коэффициентов то при любом способ релаксации сходится Нередко оказывается вероятным избрать (экспериментально) так Пусть требуется решить СЛАУ Ax=b с симметрической положительно определенной матрицей A Матрица A приводится к виду A=LLT где чтоб способ релаксации сходился значительно резвее чем Якоби либо Гаусса-Зейделя Вариант способа релаксации – разные для вычисления разных компонент еще одного -го приближения


Способы воззвания матриц

Могут быть обращены только неособенные квадратные матрицы


^ Способ Пусть требуется решить СЛАУ Ax=b с симметрической положительно определенной матрицей A Матрица A приводится к виду A=LLT где окаймления (деления на клеточки)

Начальную матрицу M размера разобьем на четыре клеточки M= где a, b, c, d – подматрицы размеров  Примем что матрица M-1 существует и может быть разбита на Пусть требуется решить СЛАУ Ax=b с симметрической положительно определенной матрицей A Матрица A приводится к виду A=LLT где клеточки так же как и матрица M те M-1 =  где A B, C, D – подматрицы размеров  Так как M*M-1=E, то *= либо

Пусть подматрица d имеет оборотную d-1  которая известна Пусть требуется решить СЛАУ Ax=b с симметрической положительно определенной матрицей A Матрица A приводится к виду A=LLT где Тогда после маленьких преобразований получим формулы которые могут быть поочередно решены относительно матриц A B, C, D:

(11)

Вычисление оборотной матрицы реализуется при помощи способа окаймления Сущность его заключается в последующем Пусть дана матрица Пусть требуется решить СЛАУ Ax=b с симметрической положительно определенной матрицей A Матрица A приводится к виду A=LLT где M = = Образуем M1=; M2=; M3= и тд

Любая последующая матрица получена из предшествующей с помощью окаймления Оборотная к первой из этих матриц находится конкретно: M1-1 =  Зная M1-1 и применив к M Пусть требуется решить СЛАУ Ax=b с симметрической положительно определенной матрицей A Матрица A приводится к виду A=LLT где2 схему вычислений (11) можно получить M2-1 а потом с помощью M2-1 аналогично получить M3-1 и тд Процесс завершается матрицей Mn-1 тк Mn-1= M-1. Воззвание можно начать и с правого нижнего Пусть требуется решить СЛАУ Ax=b с симметрической положительно определенной матрицей A Матрица A приводится к виду A=LLT где угла матрицы M.

^ Способ Ершова (способ пополнения)

На базе начальной матрицы A и единичной матрицы E строится последовательность матриц A(0), A(1)’, A(1), …., A(n)’, A(n), где A(0)=A-E,



; .

Матрица Пусть требуется решить СЛАУ Ax=b с симметрической положительно определенной матрицей A Матрица A приводится к виду A=LLT где A(n)=A(-1). Матрицы A(1)’, A(2)’, ……….., A(n)’ являются вспомогательными

Способ Фаддеева

Напомним что следом (spur) матрицы A именуется сумма ее частей на главной диагонали: SpA =  

Вычисление оборотной матрицы A-1 порядка делается по последующим Пусть требуется решить СЛАУ Ax=b с симметрической положительно определенной матрицей A Матрица A приводится к виду A=LLT где формулам:

A1=A, p1=SpA1, B1=A1-p1E;

A2=AB1, p2=(1/2)*SpA2, B2=A2-p2E;

………………………………………………………..

An-1=ABn-2, pn-1=(1/(n-1))*SpAn-1, Bn-1=An-1-pn-1E;

An=ABn-1, pn=(1/n)*SpAn Пусть требуется решить СЛАУ Ax=b с симметрической положительно определенной матрицей A Матрица A приводится к виду A=LLT где, A-1=(1/pn)*Bn-1.


Способы разложения матриц

Разложение неособенной квадратной матрицы в произведение 2-ух треугольных

Произведение обязано иметь вид A=L*U где L – нижняя треугольная матрица с единичной диагональю U – верхняя треугольная матрица Элементы матрицы L рассчитываются Пусть требуется решить СЛАУ Ax=b с симметрической положительно определенной матрицей A Матрица A приводится к виду A=LLT где по формулам:





Элементы матрицы U рассчитываются по формулам:



Вероятны два метода вычисления частей матриц U и L По столбцам поочередно рассчитываются …, По строчкам - …,


^ Разложение неособенной квадратной матрицы в произведение нижней треугольной Пусть требуется решить СЛАУ Ax=b с симметрической положительно определенной матрицей A Матрица A приводится к виду A=LLT где матрицы с единичной диагональю и матрицы с ортогональными строчками

Пусть дана действительная неособенная матрица

A = 

Из каждой -й строчки начиная со 2-ой вычитают первую строчку умноженную на некое число  зависящее от номера Пусть требуется решить СЛАУ Ax=b с симметрической положительно определенной матрицей A Матрица A приводится к виду A=LLT где преобразуемой строчки В итоге получим перевоплощенную матрицу A(1) Множители выбираются из условия ортогональности первой строчки всем остальным строчкам: Матрицу A(1) преобразуем аналогично: из каждой ее -й строчки вычитаем вторую строчку A(1) умноженную на Получим Пусть требуется решить СЛАУ Ax=b с симметрической положительно определенной матрицей A Матрица A приводится к виду A=LLT где матрицу A(2) и тд пока не получится матрица A(n-1) все строчки которой попарно ортогональны Матрица A(n-1)=R с ортогональными строчками вышла из матрицы A в итоге цепи Пусть требуется решить СЛАУ Ax=b с симметрической положительно определенной матрицей A Матрица A приводится к виду A=LLT где простых преобразований Потому справедливо равенство R=A, где  - нижняя треугольная матрица Матрицу  несложно получить проделав над единичной матрицей все преобразования совершенные над матрицей A. Потом находится -1 из условия -1= E. Итак совсем A=-1R


Разложение неособенной Пусть требуется решить СЛАУ Ax=b с симметрической положительно определенной матрицей A Матрица A приводится к виду A=LLT где симметрической матрицы в произведение 2-ух треугольных транспонированных меж собой матриц: A=T*TT

Элементы матрицы T рассчитываются по формулам:



Элементы матрицы T будут действительными если

Определитель матрицы A можно вычислить по Пусть требуется решить СЛАУ Ax=b с симметрической положительно определенной матрицей A Матрица A приводится к виду A=LLT где выражению:

det A=det T * det TT =


Пример решения СЛАУ в системе Mathcad






ЗАДАНИЕ

1. Решить СЛАУ в Mathcad’е по данному из таблицы варианту.

2. Составить метод и написать код для решения Пусть требуется решить СЛАУ Ax=b с симметрической положительно определенной матрицей A Матрица A приводится к виду A=LLT где СЛАУ способом Гаусса с частичным выбором ведущего коэффициента Данный вариант использовать для тестирования. Получить зависимости временных издержек от размера системы и усредненной точности решения от размера системы и типа представления (float, double, long Пусть требуется решить СЛАУ Ax=b с симметрической положительно определенной матрицей A Матрица A приводится к виду A=LLT где double) коэффициентов.

Таблица



варианта

Матрица коэффициентов

системы A

Столбец свободных

членов b



1

1.84 2.32 1.83

2.25 2.60 2.06

2.53 2.82 2.24

-6.09

-6.98

-5.52



2

2.58

1.32

2.09

2.93

1.55

2.25

3.13

1.58

2.34

-6.66

-3.58

-5.01



3

2.18

2.17

3.15

2.44

2.31

3.22

2.49

2.49

3.17

-4.34

-3.91

-5.27



4

1.54

3.69

2.45

1.70

3.73

2.43

1.62

3.59

2.25

-1.97

-3.74

-2.26



5

1.53

2.35

3.83

1.61

2.31

3.73

1.43

2.07

3.45

-5.13

-3.69

-5.98



6

2.36

2.51

2.59

2.37

2.40

2.41

2.13

2.10

2.06

1.48

1.92

2.16



7

3.43

4.17

4.30

3.38

4.00

4.10

3.09

3.65

3.67

5.52

6.93

7.29



8

3.88

3.00

2.67

3.78

2.79

2.37

3.45

2.39

1.96

10.41

8.36

7.62



9

3.40

2.64

4.64

3.26

2.39

4.32

2.90

1.96

3.85

13.05

10.30

17.89



10

2.53

3.95

2.78

2.36

4.11

2.43

1.93

3.66

1.94

12.66

21.97

13.93


11

2.16

3.55

4.85

1.96

3.23

4.47

1.56

2.78

3.97

13.16

21.73

29.75



12

2.69

2.73

2.93

2.47

2.39

2.52

2.07

1.92

2.02

19.37

19.43

20.80



13

3.72

4.47

4.96

3.47

4.10

4.53

3.06

3.63

4.01

30.74

36.80

40.79



14

4.35

4.04

3.14

4.39

3.65

2.69

3.67

3.17

2.17

40.15

36.82

28.10



15

4.07

2.84

4.99

3.79

2.44

4.50

3.37

1.95

3.97

40.77

27.68

49.37



16

3.19

4.43

3.40

2.89

4.02

2.92

2.47

3.53

2.40

33.91

47.21

32.92



17

2.57

4.47

4.89

2.26

4.03

4.40

1.84

3.57

3.87

28.66

50.27

55.03



18

2.83

3.00

3.72

2.50

2.55

3.21

2.08

2.07

2.68

33.28

33.59

43.43



19

3.78

4.33

4.76

3.44

3.88

4.24

3.02

3.39

3.72

46.81

53.43

58.73



20

4.59

4.83

4.06

4.24

4.36

3.53

3.82

3.88

3.01

59.54

62.33

52.11



21

4.56

3.21

4.58

4.20

2.73

4.04

3.78

2.25

3.52

61.86

42.98

61.67



22

3.75

4.18

4.43

3.39

3.70

3.88

2.97

3.22

3.36

53.38

59.28

62.62



23

2.95

5.11

4.38

2.58

4.62

3.82

2.16

4.14

3.30

44.16

46.68

65.34


24

2.93

3.47

4.78

2.55

2.98

4.22

2.14

2.50

3.70

46.41

54.78

75.81



25

3.74

4.02

4.18

3.36

3.51

3.61

2.94

3.04

3.09

63.26

67.51

70.03



26

4.67

5.30

5.11

4.28

4.79

4.54

3.87

4.32

4.03

84.43

95.45

91.69



27

4.90

3.79

4.01

4.50

3.27

3.43

4.09

2.81

2.91

94.18

71.57

75.45



28

4.25

3.86

5.40

3.84

3.34

4.82

3.43

2.87

4.30

86.07

77.12

108.97


29

3.35

5.41

3.88

2.94

4.88

3.30

2.53

4.41

2.78

70.69

115.38

81.07



30

3.05

4.14

5.63

2.64

3.61

5.03

2.23

3.14

4.52

67.17

91.43

125.40



^ ЛАБОРАТОРНАЯ РАБОТА 5


АППРОКСИМАЦИЯ ФУНКЦИИ ПО Способу

Меньших КВАДРАТОВ


Короткие сведения

При анализе эмпирических данных появляется необходимость отыскать в очевидном виде многофункциональную зависимость меж величинами и , которые получены в итоге измерений Обычно Пусть требуется решить СЛАУ Ax=b с симметрической положительно определенной матрицей A Матрица A приводится к виду A=LLT где вид этой многофункциональной зависимости известен а некие числовые характеристики закона неопознаны

Пусть к примеру функция задана в виде Задачка состоит в аппроксимации неведомой многофункциональной зависимости меж и многочленом данной степени :



Для решения Пусть требуется решить СЛАУ Ax=b с симметрической положительно определенной матрицей A Матрица A приводится к виду A=LLT где этой задачки воспользуемся способом меньших квадратов Согласно этому способу коэффициенты многочлена необходимо избрать такими чтоб сумма квадратов отклонений отысканного многочлена от данных значений функции была малой Другими словами коэффициенты должны минимизировать функцию



В Пусть требуется решить СЛАУ Ax=b с симметрической положительно определенной матрицей A Матрица A приводится к виду A=LLT где точке минимума функции её производные обращаются в нуль Дифференцируя и приравнивая нулю производные получим нормальную систему способа меньших квадратов:



Отметим что полное количество вычисляемых сумм равно 

Получена СЛАУ относительно Пусть требуется решить СЛАУ Ax=b с симметрической положительно определенной матрицей A Матрица A приводится к виду A=LLT где неведомых . Определитель этой системы отличен от нуля На практике этот способ используют только для нахождения многочленов степень которых не выше 5 При более больших степенях обычная система становится плохо обусловленной и погрешности определения Пусть требуется решить СЛАУ Ax=b с симметрической положительно определенной матрицей A Матрица A приводится к виду A=LLT где коэффициентов значительны



put-into-reported-speech-the-following-questions.html
put-k-bolee-visokomu-opitu.html
put-k-kosmicheskomu-soznaniyu.html