Метод прогонки в excel
Метод прогонки является частным случаем метода Гаусса и применяется для решения систем линейных уравнений с трёхдиагональной матрицей. Такая система, в частности, получается при построении кубического интерполяционного сплайна. Но давайте разберемся подробнее с задачами из физики, приводящими к такой конфигурации, и со способами решения.
Почему появилась необходимость решать СЛАУ с 3х-диагональными матрицами
Такие матрицы часто называют ленточными, потому что похожи на ленту, проходящую через диагональ :) Но, соблюдая математическую строгость, будем называть её трехдиагональной матрицей или матрицей Якоби. Во всех местах, кроме главной диагонали и двух соседних с ней, стоят нули.
Системы линейных алгебраических уравнений (СЛАУ) с такими матрицами встречаются при решении многих задач математической физики.
Теория разностных методов решения дифференциальных уравнений в настоящее время является обширной и самостоятельной областью вычислительной математики. Она включает развитый аппарат априорных оценок разностных решений, анализа устойчивости и сходимости, оценок погрешностей, а также специальные алгоритмы решения разностных уравнений. В то же время значительная часть таких результатов описывается в терминах матричных или векторных операций и опирается на исследования линейной алгебры.
Системы разностных уравнений являются прекрасным примером приложения теории матриц, и в значительной степени — именно трехдиагональных. В свою очередь, многочисленные актуальные задачи физики, приводящие к разностным схемам, оказались толчком для проведения новых интенсивных исследований по линейной алгебре.
По теории разностных методов есть специальная литература, например, фундаментальные монографии Марчука и Самарского.
Где такие матрицы встречаются в физике
Задачи, включающие в себя трехдиагональные системы линейных алгебраических уравнений (СЛАУ) в качестве основных или вспомогательных компонент, можно разделить на несколько типов:
1. Одномерные краевые задачи для дифференциальных уравнений второго порядка (задача Дирихле для уравнения Пуассона, задача Неймана, смешанная краевая задача);
2. Параболические задачи с одной пространственной переменной (одномерная задача нестационарной теплопроводности или диффузии );
3. Решение многомерных эллиптических и параболических уравнений (задача Дирихле для уравнения Пуассона в двумерной граничной области);
4. Решение локально-нелинейных одномерных задач (двухфазная задача Стефана);
5. Еще одним примером краевой задачи с применением трехдиагональной матрицы может служить задача Штурма-Лиувилля, заключающаяся в отыскании нетривиальных решений однородного уравнения на некотором отрезке. В свою очередь, эта задача служит постоянным источником новых идей для спектральной теории операторов и смежных вопросов анализа.
6. Применение трехдиагональных систем не ограничивается задачами математической физики, они встречаются в алгоритмах сплайновых аппроксимаций, а так же в задачах линейной алгебры, для решения проблемы собственных значений матриц общего вида.
Сами по себе матрицы общего вида применяются практически во всех областях как вычислительной математики, так и в инженерных задачах. Например, при решении задач на прочность и жесткость конструкций формируется глобальная матрица жесткости системы, в тепловых задачах матрица имеет смысл теплового сопротивления, матрицы также применяются при решении задач оптимизации и т. д. Существует целый ряд методов по сведению матриц к разряженному виду при переходе к компьютерному решению различных задач. Матрицы обычно принимают симметричный вид и нередко трехдиагональный.
Теория для программирования метода прогонки
Для решения трехдиагональных СЛАУ часто применяют метод прогонки. Основным его преимуществом является экономичность, т. е. то, что этот метод максимально использует структуру исходной системы. Недостатком метода является то, что с каждой итерацией накапливается ошибка округления.
Полученные матрицы (для СЛАУ № 1 и 2) представляют собой матрицу коэффициентов А и вектор свободных членов системы уравнений, записанной в матричной форме
(4.2)
Решение СЛАУ имеет вид
,
где А -1 – обратная матрица, полученная с помощью функции МОБР.
Значения вектора неизвестных получаются умножением обратной матрицы А -1 и вектора свободных членов с помощью функции МУМНОЖ.
СЛАУ № 1
Метод обратной матрицы
Матрица коэффициентов А
Вектор свобод. членов, b
Обратная матрица А -1
Вектор неиз-вест-
x1
x2
x3
В ячейках строки 3 записаны заголовки объектов расчета
В ячейки диапазона А4 : С6 введены значения элементов исходной матрицы коэффициентов
В ячейки диапазона Е4 : Е6 введены значения элементов вектора свободных членов
Для получения обратной матрицы необходимо выделить диапазон ячеек, в который будет размещена обратная матрица G4 : I6. Затем выбрать функцию МОБР категории Математические функции. Следуя указаниям Мастера функций, указать диапазон обращаемой матрицы А4 : С6. Нажать комбинацию клавиш Ctrl + Shift + Enter.
Выделить диапазон L4 : L6. Затем выбрать функцию МУМНОЖ категории Математические функции. Следуя указаниям Мастера функций, указать диапазоны перемножаемых элементов: матрицы G4 : I6 и вектора Е4 : Е6. Нажать комбинацию клавиш Ctrl + Shift + Enter.
Рекомендации по использованию excel для решения слау № 2 с помощью метода прогонки
СЛАУ № 2
Метод прогонки
Трехдиагональная матрица коэффициентов А
Вектор свобод. членов, d
Прогоночные коэффициенты
p0 =
q0 =
x0 =
p1 =
q1 =
x1 =
p2 =
q2 =
x2 =
p3 =
q3 =
x3 =
В ячейках диапазона А 3: С6 записаны коэффициенты трехдиагональной матрицы коэффициентов СЛАУ № 2
В ячейках диапазона F 3: F 6 записаны элементы вектора свободных членов СЛАУ № 2
В ячейках столбцов А8 : А11, С8 : С11, Е8 : Е11 записаны обозначения прогоночных коэффициентов и неизвестных
В ячейку В8 введена формула = - B3 / A3 (см. формулу метода прогонки для прогоночного коэффициента p0 = - c0 / a0)
В ячейку D8 введена формулу = F3 / A3 (см. формулу метода прогонки для прогоночного коэффициента q0 = d0 / a0)
В ячейку B9 введена формулу = - C4 / (B4+A4*$B8) (см. формулу для прогоночных коэффициентов pi )
Эти же формулы использованы для заполнения ячеек диапазона B9 : B 11
Аналогичные действия произведены для вычисления (по соответствующим формулам) прогоночных коэффициентов qi (диапазон D 8 : D 11) и вычисления неизвестных хi (диапазон F 8 : F 11)
Тут вы можете оставить комментарий к выбранному абзацу или сообщить об ошибке.
Систему линейных алгебраических уравнений можно также решить, используя надстройку «Поиск решения». При использовании данной надстройки строится последовательность приближений , i=0,1,…n.
Назовем вектором невязок следующий вектор:
Задача Excel заключается в том, чтобы найти такое приближение , при котором вектор невязок стал бы нулевым, т.е. добиться совпадения значений правых и левых частей системы .
В качестве примера рассмотрим СЛАУ (3.27).
Последовательность действий:
1. Оформим таблицу, как показано на рис.3.4. Введем коэффициенты системы (матрицу А) в ячейки А3:С5.
Рис.3.4. Решение СЛАУ с помощью надстройки «Поиск решения»
2. В ячейках А8:С8 будет сформировано решение системы (х1, х2, х3). Первоначально они остаются пустыми, т.е. равными нулю. В дальнейшем будем их называть изменяемыми ячейками.. Однако для контроля правильности вводимых далее формул, удобно ввести в эти ячейки какие-либо значения, например, единицы. Эти значения можно рассматривать как нулевое приближение решения системы, = (1, 1, 1).
3. В столбец D введем выражения для вычисления левых частей исходной системы. Для этого в ячейкуD3 введем и затем скопируем вниз до конца таблицы формулу:
D3=СУММПРОИЗВ (A3:C3;$A$8:$C$8).
Используемая функция СУММПРОИЗВ принадлежит категории Математические.
4. В столбец Е запишем значения правых частей системы (матрицу В).
5. В столбец F введем невязки в соответствии с формулой (3.29), т.е. введем формулу F3=D3-E3 и скопируем ее вниз до конца таблицы.
6. Будет не лишним проверить правильность вычислений для случая = (1, 1, 1).
7. Выберем команду Данные\Анализ\Поиск решения.
Рис. 3.5. Окно надстройки «Поиск решения»
В окне Поиск решения (рис.3.5) в поле Изменяемые ячейки укажем блок $А$8:$С$8, а в поле Ограничения – $F$3:$F$5=0. Далее щелкнем по кнопке Добавить и введем эти ограничения. И затем - кнопка Выполнить
Полученное решение систем (3.28) х1=1; х2=–1 х3=2 записано в ячейках А8:С8, рис.3.4.
Реализация метода Якоби средствами приложения MS Excel
В качестве примера рассмотрим систему уравнений (3.19), решение которой методом Якоби получено выше (пример 3.2)
Приведем эту систему к нормальному виду:
Последовательность действий
1. Оформим таблицу, как показано на рис.3.6.:
• Матрицы и (3.15)введем в ячейки В6:Е8.
• Значение e–в Н5.
• Номер итерации k сформируем в столбце А таблицы с помощью автозаполнения.
• В качестве нулевого приближения выберем вектор
= (0, 0, 0) и введем его в ячейки В11:D11.
2. Используя выражения (3.29), в ячейки В12:D12 запишем формулы для вычисления первого приближения:
Эти формулы можно записать иначе, используя функцию Excel СУММПРОИЗВ.
В ячейку Е12 введем формулу: E12=ABS(B11-B12) и скопируем ее вправо, в ячейки F12:G12.
Рис.3.6. Схема решения СЛАУ методом Якоби
3. В ячейку Н12 введем формулу для вычисления M (k) , используя выражение (3.18): Н12 = МАКС(E12:G12). Функция МАКС находится в категории статистические.
4. Выделим ячейки В12:Н12 и скопируем их вниз до конца таблицы. Таким образом, получим k приближений решения СЛАУ.
5. Определим приближенное решение системы и количество итераций, необходимое для достижения заданной точности e.
Для этого оценим степень близости двух соседних итераций по формуле (3.18). Воспользуемся Условным форматированиемв ячейках столбца.
Результат такого форматирования виден на рис.3.6. Ячейки столбца Н, значения которых удовлетворяют условию (3.18), т.е. меньше e=0,1, тонированы.
Анализируя результаты, принимаем за приближенное решение исходной системы с заданной точностью e=0,1 четвертую итерацию, т.е.
Исследуем характер итерационного процесса. Для этого выделим блок ячеек А10:D20 и, используя Мастер диаграмм, построим графики изменения каждой компоненты вектора решения в зависимости от номера итерации,
Приведенные графики (рис.3.7) подтверждают сходимость итерационного процесса.
Рис. 3.7. Иллюстрация сходящегося итерационного процесса
Изменяя значение eв ячейке Н5, получим новое приближенное решение исходной системы с новой точностью.
Реализация метода прогонки средствами приложения Excel
Рассмотрим решение следующей системы линейных алгебраических уравнений методом «прогонки», используя таблицы Excel.
Векторы:
Последовательность действий
1. Оформим таблицу, как показано на рис.3.8. Исходные данные расширенной матрицы системы (3.30), т.е. вектора введем в ячейки B5:E10.
2. Про гоночные коэффициенты U0=0 и V0=0 введем в ячейки G4 и H4 соответственно.
3. Вычислим прогоночные коэффициенты Li, Ui, Vi. Для этого в ячейках F5, G5, H5 вычислим L1, U1, V1. по формуле (3.8). Для этого введем формулы:
F5 = B5*G4+C5; G5=-D5/F5, H5 = (E5-B5*H4)/F5, и затем скопируем их вниз.
Рис.3.8. Расчетная схема метода «прогонки»
4. В ячейке I10 вычислим x6 по формуле (3.10)
5. По формуле (3.7) вычислим все остальные неизвестные x5 x4, x3, x2, x1. Для этого в ячейке I9 вычислим x5 по формуле (3.6): I9=G9*I10+H9 . А далее копируем эту формуле вверх.
Контрольные вопросы
1. Система линейных алгебраических уравнений (СЛАУ). Что является решением СЛАУ. Когда существует единственное решение СЛАУ.
2. Общая характеристика прямых (точных) методов решения СЛАУ. Методы Гаусса и прогонки.
3. Общая характеристика итерационных методов решения СЛАУ. Методы Якоби (простых итераций) и Гаусса-Зейделя.
4. Условия сходимости итерационных процессов.
5. Что понимают под терминами обусловленности задач и вычислений, корректности задачи решения СЛАУ.
Глава 4.
Численное интегрирование
При решении достаточно большого круга технических задач приходится сталкиваться с необходимостью вычисления определенного интеграла:
Вычисление площадей, ограниченных кривыми, работы, моментов инерции, перемножение эпюр по формуле Мора и т.д. сводится к вычислению определенного интеграла.
Если непрерывная на отрезке [a, b] функция y = f(x) имеет на этом отрезке первообразную F(x), т.е. F ’ (x) = f(x) , то интеграл (4.1) может быть вычислен по формуле Ньютона – Лейбница:
Однако, только для узкого класса функций y=f(x) первообразная F(x) может быть выражена в элементарных функциях. Кроме того, функция y=f(x) может задаваться графически или таблично. В этих случаях применяют различные формулы для приближенного вычисления интегралов.
Такие формулы называют квадратурными формулами или формулами численного интегрирования.
Формулы численного интегрирования хорошо иллюстрируются графически. Известно [1, 12], что значение определенного интеграла (4.1) пропорционально площади криволинейной трапеции, образованной подынтегральной функцией y=f(x), прямыми х=а и х=b, осью ОХ (рис.4.1).
Задачу вычисления определенного интеграла (4.1) заменяем задачей вычисления площади этой криволинейной трапеции. Однако задача нахождения площади криволинейной не является простой.
Отсюда идея численного интегрирования [3, 6] будет заключатся в замене криволинейной трапеции фигурой, площадь которой вычисляется достаточно просто.
| y=f(x) |
| y |
| x |
| xi |
| xi+1 |
| xn=b |
| xо=a |
| Si |
Рис.4.1. Геометрическая интерпретация численного интегрирования
Для этого отрезок интегрирования [a, b] разобьем на n равных элементарных отрезков [xi ,xi+1] (i=0, 1, 2, …. n-1), с шагом h=(b-a)/n. При этом криволинейная трапеция разобьется на n элементарных криволинейных трапеций с основаниями равными h (рис.4.1).
Каждая элементарная криволинейная трапеция заменяется фигурой, площадь которой вычисляется довольно просто. Обозначим эту площадь Si . Сумма всех этих площадей называется интегральной суммой и вычисляется по формуле
Тогда приближенная формула вычисления определенного интеграла (4.1) имеет вид
Точность вычисления по формуле (4.4) зависит от шага h, т.е. от числа разбиений n. С увеличением n интегральная сумма приближается к точному значению интеграла
Это хорошо проиллюстрировано на рис.4.2.
| n |
| бn |
| J |
| Точное значение интеграла |
Рис.4.2. Зависимость точности вычисления интеграла
от числа разбиений
В математике доказывается теорема: если функция y=f(x) непрерывна на [a, b], то предел интегральной суммы бn существует и не зависит от способа разбиения отрезка [a,b] на элементарные отрезки.
Формулу (4.4) можно использовать, если известна степень точности такого приближения. Существуют различные формулы для оценки погрешности выражения (4.4), но, как правило, они достаточно сложны. Будем проводить оценку точности приближения (4.4) методом половинного шага.
метод прогонки С++
Запрограммировать краевую задачу методом прогонки(тридиагональнои матрицы) Добавлено через 4.
Метод прогонки
Здравствуйте, пытаюсь реализовать метод прогонки, не могу проверить работу, не понимаю как.
Метод обратной прогонки
Нужно реализовать метод обратной прогонки на с++.МОЖНО ВЗЯТЬ ЛЮБОЙ ПРИМЕР.КТО МОЖЕТ ПОМОГИТЕ!!
Можно вы поможете реализовать так чтоб я еще и размерности матриц задавал?? Можно вы поможете реализовать так чтоб я еще и размерности матриц задавал?? Trainer, помогите правильно сделать, будьте любезны?) Если я правильно понял, то матрица А должна иметь одинаковое число столбцов и строк, а матрица В - то же число строк, правильно? Размерность не больше 50. Хотя дин. массивы использовать правильней. Trainer, в чем смысл использования глобальных переменных? Ни в чем, я не обратил внимание. Как было в предложенном примере, так я и оставил.
Их можно сделать и локальными, ничего не изменится конкретно в этом проекте. Alexandr1966, Так все-таки, надо было делать динамическое выделение памяти или нет?
Можно вы поможете реализовать так чтоб я еще и размерности матриц задавал??
Да в принципе хоть как)))
Добавлено через 2 часа 31 минуту
А вот в этом методе прогонки матрицу А когда ввёл, она потом переворачивает столбцы и строки, так надо да в этом методе?
И вот матрицу В когда ввел допустим 1 2 3, она выводит её 0 1 2, так тоже надо в этом методе?
просто я не очень разбираюсь подскажите?
Добавлено через 38 минут
Ребят подскажите Trainer, zss
Trainer, zss, Ребята, вот смотрите, программа вот эта работает неправильно, что-то в ней не так.
Вот пример с ответами который взят из задачника, он правильно решенный:
Матрица А:
1 0 0 0
1 -2 1 0
0 1 -2 1
0 0 0 1
Матрица В:
0
0
0
2
Матрица Х (ответы):
0
0,66667
1,3333
2
Вот код, который я проверяю, подскажите что неправильно работает пожалуйста, видимо где-то матрицы обе переворачиваются в коде + вывод введённых матриц неправильный.
Alexandr1966, если выводит не то, что ввели значит напутали с индексацией.
Вот тут:
У вас A[k][i] вместо A[i][k];
зачем-то начинаете заполнять с 1, хотя везде используете 0.В итоге:
Метод прогонки для СЛАУ
Народ, я почти умер. Писал метод прогонки, работает неправильно, выдает что-то близкое, но.
Метод прямой прогонки. Динамическое программирование
надо написать прогу, которая искала бы кратчайший путь из одного конца неориентированного графа в.
Динамическое программирование. Метод прямой прогонки
Мне нужно реализовать граф с поиском минимального пути из начала графа в конец путем прямой.
Читайте также: