Метод халецкого в excel
Пусть требуется решить систему линейных алгебраических уравнений
с симметричной положительно определенной матрицей А. Линейные системы такого типа часто встречаются в приложениях (например, в задачах оптимизации, при решении уравнений математической физики и др.). Для их решения весьма часто применяется метод Холецкого (другое название — метод квадратных корней).
В основе метода лежит алгоритм построения специального LU-разложения матрицы А, в результате чего она приводится к виду
В разложении (5.64) нижняя треугольная матрица
уже не обязательно должна иметь на главной диагонали единицы, как это было в методе Гаусса, а требуется только, чтобы диагональные элементы были положительными.
Если разложение (5.64) получено, то решение системы (5.63) сводится к последовательному решению двух систем с треугольными матрицами:
Для решения систем (5.66) требуется выполнение примерно арифметических операций.
Найдем элементы матрицы Для этого вычислим элементы матрицы и приравняем их соответствующим элементам матрицы А. В результате получим систему уравнений
Решая систему (5.67), последовательно находим
Заметим, что для вычисления диагональных элементов используется операция извлечения квадратного корня. Поэтому метод Холецкого
называют еще и методом квадратных корней. Доказано, что положительность соответствующих подкоренных выражений является следствием положительной определенности матрицы А.
2. Достоинства метода.
Метод Холецкого обладает рядом ценных качеств, которые позволяют предпочесть его методу Гаусса, если требуется решить систему линейных алгебраических уравнений с симметричной и положительно определенной матрицей.
Как нетрудно подсчитать, число операций, выполняемых в ходе вычисления разложения (5.64) по формулам (5.68), равно примерно Учитывая, что для решения систем (5.66) требуется примерно арифметических операций, убеждаемся, что при больших метод Холецкого требует вдвое меньше вычислительных затрат по сравнению с методом Гаусса.
Учет симметричности матрицы А позволяет экономно использовать память ЭВМ при записи исходных данных задачи и результатов вычислений. Действительно, для задания матрицы А достаточно ввести в память ЭВМ только элементы расположенные на главной диагонали и под ней. В формулах (5.68) каждый такой элемент используется лишь однажды для получения и далее в вычислениях не участвует. Поэтому в процессе вычислений найденные элементы могут последовательно замещать элементы
В результате нижняя треугольная матрица может быть расположена в той области памяти, где первоначально хранилась нижняя треугольная часть матрицы А. Применение для решения системы (5.63) метода Гаусса потребовало бы использования примерно вдвое большего объема памяти.
Безусловным достоинством метода Холецкого является также его гарантированная устойчивость.
Пример 5.16. Используя метод Холецкого, найдем решение системы уравнений с симметричной положительно определенной матрицей:
Метод простой итерации даёт возможность получить последовательность приближённых значений, сходящуюся к точному решению системы.
Преобразуем систему (3.1) к нормальному виду:
. (3.2)
Правая часть системы (3.2) определяет отображение:
x=(x1, x2, . xn), преобразующее точку n -мерного метрического пространства в точку y=(y1, y2, . yn) того же пространства.
Выбрав начальную точку x 0 =(x 0 1, x 0 2, . x 0 n), можно построить итерационную последовательность точек n - мерного пространства: x 0 , x 1 =F(x 0 ), . , x n+1 =F(x n )
При определённых условиях данная последовательность сходится.
Так, для исследования сходимости таких последовательностей используется принцип сжимающих отображений, который состоит в следующем.
Если F– сжимающее отображение, определённое в полном метрическом пространстве с метрикой ρ(x,y), то существует единственная неподвижная точка x*, такая, что x*=F(x*). При этом итерационная последовательность, n>, полученная с помощью отображения F с любым начальным членом х (0) , сходится к x*.
Оценка расстояния между неподвижной точкой x* отображения F и приближением х (к) даётся формулами:
(3.3)
где α – множитель, определяемый достаточными условиями сжимаемости отображения F.
Значение множителя α, определяется выбором метрики, в которой проверяется сходимость последовательности значений xi.
Рассмотрим достаточные условия сходимости итерационной последовательности n>.
Практически, для применения метода итерации систему линейных уравнений удобно "погрузить" в одну из трёх следующих метрик:
(3.4)
Для того, чтобы отображение F, заданное в метрическом пространстве соотношениями (3.2), было сжимающим, достаточно выполнение одного из следующих условий:
а) в пространстве с метрикой ρ1: , т. е. максимальная из сумм модулей коэффициентов в правой части системы (3.2), взятых по строкам, должна быть меньше единицы.
б) в пространстве с метрикой ρ2: , т. е. максимальная из сумм модулей коэффициентов в правой части системы (3.2), взятых по столбцам, должна быть меньше единицы.
в) в пространстве с метрикой ρ3: , т. е. сумма квадратов при неизвестных в правой части системы (3.2) должна быть меньше единицы
Пример . Вычислить два приближения методом простой итерации. Оценить погрешность второго приближения. В качестве начального приближения выбрать x 0 =(0; 0; 0).
Так как диагональные элементы системы являются преобладающими, то приведем систему к нормальному виду:
Последовательные приближения будем искать по формулам:
Получаем:
x 1 =(-1.9022; 0.4889; 2.1456), x 2 =(-1.1720; 0.6315; 1.2389).
Для оценки погрешности в метрике ρ1 вычисляем коэффициент μ
.
Вычисляем погрешность:
При большом числе неизвестных схема метода Гаусса, дающая точное решение, становится весьма сложной. В этом случае для решения СЛАУ иногда удобнее пользоваться методом простой итерации.
Метод итераций для системы уравнений в Excel
На листе Excel организуется таблица в три зоны: первая зона состоит из одного столбца (номер итерации), вторая зона определяет переменные x , третья зона под вычисления точности epsilon .
Во второй зоне по итерационной схеме организуется расчет переменных x (в примере для случая трех переменных):
Итерация №1: =$F$2/$B$2-C6*$C$2/$B$2-D6*$D$2/$B$2;=$F$3/$C$3-B6*$B$3/$C$3-D6*$D$3/$C$3;=$F$4/$D$4-B6*$B$4/$D$4-C6*$C$4/$D$4
Итерация №2: =$F$2/$B$2-C7*$C$2/$B$2-D7*$D$2/$B$2;=$F$3/$C$3-B7*$B$3/$C$3-D7*$D$3/$C$3;=$F$4/$D$4-B7*$B$4/$D$4-C7*$C$4/$D$4
Решить систему линейных алгебраических уравнений, используя точный метод численного решения (схему Халецкого).
Введение
Существует несколько способов решения таких систем, которые в основном делятся на два типа: 1) точные методы, представляющие собой конечные алгоритмы для вычисления корней системы, 2) итерационные методы, позволяющие получать корни системы с заданной точностью путем сходящихся бесконечных процессов.
Для того чтобы система линейных алгебраических уравнений имела решение, необходимо и достаточно, чтобы ранг основной матрицы был равен рангу расширенной матрицы. Если ранг основной матрицы равен рангу расширенной матрицы и равен числу неизвестных, то система имеет единственное решение. Если ранг основной матрицы равен рангу расширенной матрицы, но меньший числа неизвестных, то система имеет бесконечно решений.
Пример системы линейных уравнений:
Или в матричном виде: ,
где матрица коэффициентов системы;
- вектор неизвестных; - вектор свободных членов.
Точные методы решения СЛАУ
Метод главных элементов.
Пусть дана система линейных алгебраических уравнений. Рассмотрим расширенную матрицу, состоящую из коэффициентов системы a[i,j] и свободных членов b[i]. Метод главных элементов - это обобщение метода исключения переменных (метода Гаусса). Обозначим матрицу, состоящую из коэффициентов при неизвестных и столбца свободных членов исходной системы за M.
Выбираем наибольший по модулю элемент, не принадлежащий столбцу свободных членов. Пусть это будет . Этот элемент называется главным элементом, а строка, в которой он находится, называется главной строкой.
Далее производим следующие преобразования: к каждой неглавной строке прибавим главную строку, умноженную на соответствующий множитель для этой строки. В результате мы получим матрицу, у которой q-й столбец состоит из нулей. Отбросим этот столбец и главную p-ю строку, получим новую матрицу с меньшим на единицу числом строк и столбцов. Над матрицей повторяем те же операции, после чего получаем матрицу и т.д. Таким образом, мы построим последовательность матриц
последняя, из которых представляет двучленную матрицу - строку, её также будем считать главной строкой. Для определения неизвестных объединяем в систему все главные строки, начиная с последней. После надлежащего изменения нумерации неизвестных получается система с треугольной матрицей, из которой легко шаг за шагом найти неизвестные данной системы.
Заметим, что метод Гаусса является частным случаем, метода главных элементов, а схема метода Гаусса получается, если за главный элемент всегда выбирать левый верхний элемент соответствующей матрицы. Запрограммировать метод главных элементов непросто, поэтому чтобы уменьшить вычислительную погрешность, применяют метод Гаусса с выбором главного элемента. Необходимое условие применения метода главных элементов: определитель системы не равен нулю.
· Обнуляем вспомогательные матрицы B и C.
· Задаем первый столбец B и первую строку C по формулам (3.7) и (3.8).
· Вычисляем остальные элементы матриц B и C.
Þ Перебор строк (цикл i от 1 до N)
Þ Перебор столбцов (цикл j от 1 до N)
Þ Если , то вычисляем по формуле (3.7).
Þ Если , положим .
Þ Если , то вычисляем по формуле (3.8).
Þ Конец перебора строк и столбцов.
· Проверяем правильность вычисления матриц B и C. Для этого достаточно вычислить произведение и сравнить с A.
· Определим вектор y по формуле (3.9).
· Вычислим решение x по формуле (3.10).
· Выведем матрицу A и вектор правой части f, решение x и невязку Ax-f на экран.
Вычисление невязки решения
Для проверки правильности решения системы линейных алгебраических уравнений необходимо вычислить невязку решения. Невязка v является вектором и вычисляется по формуле
, (3.11)
где - приближенное решение системы уравнений Ax=f.
Если решение является точным решением, то невязка v будет равна нулевому вектору. При решении задачи на компьютере, точное решение получить практически невозможно из-за ошибок округления. Приближенное решение является приемлемым, если его невязка не будет превосходить заранее заданной погрешности Eps. Обычно погрешность Eps равна 0.001, но это значение можно изменять в зависимости от поставленной задачи и требуемой точности решения.
Итерационные методы
Итерационные методы основаны на построении итерационной последовательности , сходящейся к искомому решению системы .
Каждый такой метод характеризуется своей итерационной формулой, позволяющей вычислять очередное приближение по ранее найденным.
В простейшем случае при вычислении используется только одно приближение . Такие методы называют одношаговыми или двухслойными. Итерационную формулу для одношаговых методов принято записывать в стандартной канонической форме.
. (3.12)
где - итерационный параметр ( >0), - вспомогательная невырожденная матрица.
Метод называется стационарным, если для и .
Стационарные методы - наиболее простые с точки зрения организации вычислительного процесса. Однако нестационарные методы имеют другие преимущества, связанные с выбором и для ускорения сходимости итерационного процесса.
Определение очередного приближения с помощью итерационной процедуры (3.12) требует решения уравнения
, (3.13)
.
Такую процедуру приходится выполнять на каждом шаге. Поэтому итерационный метод можно применять при условии, что определение отдельных членов итерационной последовательности требует существенно меньшего объема вычислений, чем прямое решение исходной системы. Это накладывает ограничения на выбор матрицы .
Самый простой случай, когда . Тогда формула (3.13) приобретает вид
. (3.14)
Итерационные методы, со схемой вычислений (3.14), называются явными.
Среди неявных методов ( ) наибольшее распространение получили методы с треугольной матрицей .
Разность между приближенным решением и точным решением называется погрешностью .
Погрешность удовлетворяет итерационной формуле:
.
Итерационный процесс сходится , если при .
Матрица называется транспонированной матрицей , что записывается , если для всех .
Матрица называется симметричной ( ), если для всех .
Матрица называется положительно определенной ( ), если для имеем .
Матрица называется матрицей с диагональным преобладанием, если ее элементы удовлетворяют неравенству:
Лекции
Лабораторные
Справочники
Эссе
Вопросы
Стандарты
Программы
Дипломные
Курсовые
Помогалки
Графические
Доступные файлы (1):
Новосибирский Государственный Технический Университет
Кафедра Экономической Информатики
Курсовая работа
Тема: Исследование метода Халецкого для СЛАУ
Преподаватель: Сарычева О.М.
Новосибирск, 2002 г.
1. Постановка задачи, математическая формулировка метода………..…4
2. Описание программного обеспечения……………………………….….7
3. Описание тестовых задач………………………………………………. 9
Введение
Целью данного проекта является исследование метода Халецкого для решения систем линейных алгебраических уравнений. В ходе работы будет приведена математическая интерпретация метода, создана программа на языке программирования Turbo PASCAL, и выведены необходимые зависимости в графической форме с использованием матрично-ориентированной системы MatLAB. Будут проанализированы результаты и сделаны соответствующие выводы.
^ Исходные данные для проектирования:
Исследовать влияние мерности матрицы А, её обусловленности, разрешённости на точность полученного решения (оценивается по невязке ∑ = AX – b, где X – полученное решение).
Перечень графического материала:
График зависимости точности полученного решения от мерности матрицы А.
^ Постановка задачи, математическая формулировка метода
Рассмотрим систему линейных уравнений, записанную в матричном виде:
Ах = b,
где A=(аij)—квадратная матрица порядка n (i, j=1, 2, …, n) и
-
векторы-столбцы.
Представим матрицу A в виде произведения нижней треугольной матрицы В и верхней треугольной матрицы С с единичной диагональю, т.е. А=ВС, где
Тогда элементы bij и сij будут определяться по формулам
(1)
(2)
Исходное уравнение можно записать в следующем виде:
Произведение Сx (матрицы С на вектор-столбец x) является вектором-столбцом, который обозначим через y:
Отсюда искомый вектор x может быть вычислен из цепи уравнений Ву=b, Сх=у (3)
Так как матрицы В и С треугольные, то системы (3) легко решаются, а именно:
(4)
(5)
Из формул (4) видно, что числа уi выгодно вычислять вместе с коэффициентами cij. Эта схема вычислений называется схемой Халецкого. В схеме применяется обычный контроль с помощью сумм.
Схема Халецкого удобна для работы на клавишных вычислительных машинах, так как в этом случае операции «накопления» (1) и (2) можно проводить без записи промежуточных результатов.
Пример. Решить систему:
3x1 - x2 - x3 + 2x4 = 6
-5x1- x2 + 3x3 - 4x4 = -12
x1- 5x2 + 3x3 - 3x4 = 3
Решение.
Результаты вычислений записываем в табл. 1. Она состоит из двух частей:
1) левая половина, в которой дается схема записи результатов вычислений;
2) правая половина, в которой записываются результаты вычислений согласно указанной схеме.
^ Порядок заполнения таблицы.
1) В первый раздел табл. 1 вписываем матрицу коэффициентов системы, ее свободные члены и контрольные суммы.
2) Элементы столбца х1 из раздела I переносим в столбец х1 раздела II, так как bi1=а i1 (i=1, 2, 3, 4).
3) Вычисляем элементы первой строки раздела II. Для этого делим все элементы первой строки раздела I на элемент а11 = b11, в нашем случае на 3.
4) Заполняем столбец х2 раздела II, начиная со второй строки. Пользуясь формулами (1), определяем bj2.
5) Заполняем вторую строку раздела II, определяя с2j для j=3, 4, 5, 6 по формулам (2):
6) Заполняем столбец Х3, вычисляя его элементы b33 и b43 по формулам (1).
7) Аналогично продолжаем процесс до тех пор, пока не будет заполнен раздел II.
Таким образом, заполнение раздела II происходит способом «ёлочки»: столбец—строка, столбец—строка и т. д.
8) Определяем уi и хi (i=1, 2, 3, 4) по формулам и записываем в раздел III:
9) Текущий контроль осуществляем с помощью столбца ∑, над которым производим те же действия, что и над столбцом свободных членов.
^ 2. Описание программного обеспечения
В качестве основного языка программирования для решения СЛАУ по методу Халецкого был выбран язык Turbo PASCAL. Программа, производящая все необходимые расчёты, дана ниже с комментариями:
Program XALETSKI;
Uses Crt;
Const n=2 < Число уравнений в системе >;
Type Masiv = array[1..n] of real;
Var A:array[1..n,1..n+1] of real;
B:array[1..n,1..n] of real;
C:array[1..n,1..n+1] of real;
Writeln(' КОЭФФИЦИЕНТЫ УРАВНЕНИЙ: ');
for j:=1 to n+1 do
Writeln(fl,' ИСХОДНАЯ МАТРИЦА');
for j:=1 to n do Write(fl,A[i,j]:6:3,' * X',j,' ');
и определение коэффициентов c1,j >
for i:=1 to n do B[i,1]:=A[i,1];
Sum:=Sum + B[i,k] * C[k,j];
Sum:=Sum + B[i,k] * C[k,j];
Sum1:=Sum1 + B[i,k] * Y[k];
C[i,j]:=1 / B[i,i] * (A[i,j] - Sum);
Y[i]:=1 / B[i,i] * (A[i,n+1] - Sum1);
for i:=n-1 downto 1 do
Sum:=Sum + C[i,k] * X[k];
END.
Программа универсальна, т. к. она получает решение по методу для любого количества уравнений в системе.
Демонстрация работы программы:
Решим пример, рассмотренный подробно в первой части (стр. 5):
3x1 - x2 - x3 + 2x4 = 6
-5x1- x2 + 3x3 - 4x4 = -12
x1- 5x2 + 3x3 - 3x4 = 3
Ввод данных на последующую обработку:
Полученное решение (начиная с максимального индекса):
Это в точности совпадает с ранее полученным решением.
Матрица А называется плохо обусловленной, если существует такая матрица В, что при небольших возмущениях коэффициентов матриц А и В произойдут большие изменения в Х = А ∙В. Система А ∙ Х = В плохо обусловлена, когда матрица А плохо обусловлена. В этом случае численные методы приближённого вычисления могут привести к большим ошибкам.
Плохая обусловленность возникает тогда, когда матрица А “почти вырождена” и определитель а близок к нулю. Плохая обусловленность
также имеет место в системах двух уравнений, когда две линии почти параллельны.
К прямым методам, использующим свойство разрешенности А, можно отнести: алгоритм минимальной степени, алгоритм минимального дефицита, древовидное блочное разбиение для асимметричного разложения, методы вложенных или параллельных сечений и др., что напрямую к исследуемому методу не относится.
Исследование влияния мерности матрицы А на точность полученного решения
Для проведения необходимого исследования определим входные параметры, задающие текущие состояния матрицы, исходя из того, что необходимо исключить влияние остальных признаков.
Оценку проведём по невязке ∑ = А ∙ Х – В, где Х – полученное решение.
Начиная с двухмерной матрицы будем производить её последовательное наращивание до мерности n = 10 по следующему шаблону:
Выбор чисел случаен, т. к. это отражает более истинное влияние мерности матрицы на точность получаемого решения.
По аналогичному принципу наращиваем матрицу В (матрица-столбец свободных членов), т. е. В для
n
= 10 имеет вид:
Решения, полученные программой (индекс у Х – текущая мерность матрицы):
X2 = X3 = X4 =
-0.71429 2.23810 2.72414
0.85714 -5.04762 -9.05747
X5 = -0.85057
-1.07016
X6 = X7 = X8 = X9 = X10 =
-1.6457 -2.6659 0.4816 -12.9194 2.5455
-16.1784 -32.2604 -2.3883 -46.3986 4.0419
13.5956 31.9167 0.8037 23.2784 -2.8554
-14.2753 -33.6703 0.4085 -17.2257 2.4474
-7.5735 -16.3797 0.0168 -3.5706 0.5716
18.6508 41.7992 0.6833 17.8948 -2.0347
-6.3200 0.9089 26.3874 -2.2296
- 0.6002 -24.8276 2.7132
Точность решения оцениваем так: Е1 = ∑ ε и Е2 = max │ε │.
X=[2 3 4 5 6 7 8 9 10]
Y
=[0.7 0.81 1.53 2.44 4.28 6.43 7.42 7.83 7.92]
plot(X,Y)
Строим вторую зависимость:
X=[2 3 4 5 6 7 8 9 10]
Y=[0.1 0.2 0.4 0.5 1.08 1.1 0.6 0.7 0.3]
p
lot(X,Y)
^ 4. Анализ результатов
Видим, что при увеличении мерности матрицы происходит неоднозначное изменение зависимости полученного решения. Максимальные значения величины ошибки приходится на n = 6, 7. До этого значения n ошибка увеличивается скачкообразно. После этого значения Е2 (погрешность отдельно взятого решения) стремится к определённому значению, лежащему в пределах 0,3-0,7 (∙10 ), хотя наблюдается тенденция к её дальнейшему снижению. Так и ошибка Е1 перестаёт значительно расти, приобретая приращение, измеряемое десятыми долями (с условием того, что погрешность решения имеет порядок 10 ).
Заключение
В ходе выполнения работы был изучен метод Халецкого для систем линейных алгебраических уравнений. В ходе реализации проекта и проведения тестирования была проверена справедливость теоретических выкладок, получены сведения о зависимости точности полученного решения от ряда признаков.
^
Список литературы
1. Сарычева О.М. Численные методы. – Новосибирск, 1995. – 65с.
2. Бахвалов Н.С. Численные методы. Ч1.- М: Наука, 1975. – 632с., ил.
3. Копченова Н.В., Марон И.А. Вычислительная математика в примерах и задачах . – М: Наука, 1972. - 368с.
Читайте также: