Лекция 6

Метод взвешенных невязок

Метод наименьших квадратов довольно прост по своей идее. Однако большее распространение получил так называемый метод взвешенных невязок . В этом методе система уравнений для определения неизвестных коэффициентов строится следующим образом:

Здесь ‑ некоторая система «весовых» функций. Отсюда, кстати, и название «метод взвешенных невязок».

Математический смысл этого подхода состоит в следующем. Обратите внимание, что интегралы в (28) представляют собой скалярные произведения функции невязок на весовые функции. Если использовать геометрическую аналогию, то можно сказать, что интегралы в (28) представляют собой проекции функции невязок на весовые функции.

Если бы можно было в качестве весовых функций использовать полную систему функций, то полученное решение было бы точным. Однако, по понятным причинам, приходится использовать конечное число весовых функций.

Запишем систему (28) применительно к рассматриваемому примеру (1):

То есть, вновь, как и в методе наименьших квадратов, задача сводится к решению системы линейных уравнений . Но элементы матрицы и вектора имеют иной вид:

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

Напомним, что мы обязаны ограничиться только тремя весовыми функциями, поскольку в этом примере мы ищем приближенное решение в виде линейной комбинации трех функций (18), и приближенное решение (17) содержит три неизвестных коэффициента: .

Подставляя (18) и (31) в (30), получим

и решение системы :

Подставляя найденные значения коэффициентов в (17), получим

Таблица 3

x	Точное решение	Метод взвешенных невязок (весовые функции: 1,x ,x 2)

0.25	-0.0716449	-0.0611209
0.5	-0.1013212	-0.0780438
0.75	-0.0716449	-0.0565199

Соответствующий график на рисунке 9.

Рис.9

Как видим, результаты оказались хуже, чем при использовании, как метода конечных разностей, так и метода наименьших квадратов. Причина такой неприятности не в том, что плох метод взвешенных невязок. Дело в том, что система весовых функций была выбрана неудачно. Как уже говорилось, в «Математическом отступлении» (втором пункте этого параграфа) эти функции и не нормированы, и не ортогональны. Там же была получена по методу Грама-Шмидта ортонормированная система функций, эквивалентная (31). Попробуем теперь в качестве весовых функций использовать функции этой системы:

В этом случае матрица и вектор :

а решение системы :

В результате подстановки этих значений в (17):

Таблица 4

x	Точное решение	Метод взвешенных невязок (ортонормированная система степенных функций)

0.25	-0.0716449	-0.0717608
0.5	-0.1013212	-0.1010489
0.75	-0.0716449	-0.717608

Здесь видно, что, казалось бы, незначительное улучшение при выборе весовых функций привело к значительному повышению точности приближенного решения. Кстати, обратите внимание, что хотя матрицы и , полученные по методу наименьших квадратов и в последнем случае, различны, решения этих линейных систем практически совпали. График приближенного решения, поэтому не приводится. Он выглядел бы точным повторением рис.8.

Большая группа методов приближенного решения дифференциальных

уравнений базируется на математической формулировке, связанной с

интегральным представлением взвешенной невязки. Эту группу методов называют методами взвешенных невязок .

Пусть имеется дифференциальное уравнение и граничное условие к нему:

Здесь L −дифференциальный оператор; x i − пространственные координаты; V и S − объем и внешняя граница исследуемой области; u 0 – точное решение.

при этом коэффициенты − неизвестные величины, подлежащие определению с помощью некоторой математической процедуры.

В методах невязки эта процедура состоит из двух последовательных этапов. На первом этапе подстановкой приближенного решения (2.1.3) в уравнение (2.1.1) находится функция ошибка , или невязка , которая характеризует степень отличия от точного решения :

В итоге получается алгебраическое уравнение, содержащее текущие координаты и М по-прежнему неизвестных коэффициентов .

На втором этапе на функцию невязки (2.1.4) накладываются требования, которые минимизируют или саму невязку (метод коллокаций), или взвешенную невязку (метод наименьших квадратов и метод Галеркина).

В методе коллокаций полагают, что дифференциальное уравнение удовлетворяется только в некоторых выбранных (произвольно) точках − точках коллокаций , количество которых равно числу неизвестных коэффициентов . В этих М точках невязка должна равняться нулю, что приводит к системе М алгебраических уравнений для М коэффициентов :

В методах взвешенной невязки сначала формируют взвешенную невязку путем ее умножения на некоторые весовые функции , а затем минимизируют ее в среднем:

В методе наименьших квадратов − методе Рэлея-Ритца − в качестве весовой функции выбирается сама ошибка, т.е. , и требуется, чтобы полученная таким способом величина (функционал) была минимальна:

Для этого должно выполняться условие:

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

В методе Галеркина в качестве весовых функций берутся сами функции, называемые базисными , и требуется их ортогональность невязке :

Если − линейный оператор, то система (2.1.9) переходит в систему алгебраических уравнений относительно коэффициентов .

Рассмотрим метод Галеркина на конкретном примере . Дано уравнение на промежутке :

Сопоставление приближенных результатов, полученных различными методами, с точным решением дано в таблице 1.

50. ЯВНЫЕ И НЕЯВНЫЕ РАЗНОСТНЫЕ СХЕМЫ. МЕТОД ВЗВЕШЕННЫХ НЕВЯЗОК. МЕТОД БУБНОВА-ГАЛЕРКИНА.

Разностная схема - это конечная система алгебраических уравнений , поставленная в соответствие какой-либо дифференциальной задаче, содержащей дифференциальное уравнение и дополнительные условия (например краевые условия и/или начальное распределение). Таким образом , разностные схемы применяются для сведения дифференциальной задачи, имеющей континуальный характер, к конечной системе уравнений, численное решение которых принципиально возможно на вычислительных машинах. Алгебраические уравнения , поставленные в соответствие дифференциальному уравнению получаются применением разностного метода , что отличает теорию разностных схем от других численных методов решения дифференциальных задач (например проекционных методов, таких как метод Галёркина).

Решение разностной схемы называется приближенным решением дифференциальной задачи.

Хотя формальное определение не накладывает существенных ограничений на вид алгебраических уравнений , но на практике имеет смысл рассматривать только те схемы, которые каким-либо образом отвечают дифференциальной задаче. Важными понятиями теории разностных схем являются понятия сходимости, аппроксимации , устойчивости, консервативности.

Явные схемы

Явные схемы вычисляют значение результата через несколько соседних точек данных. Пример явной схемы для дифференцирования: (2-й порядок аппроксимации). Явные схемы часто оказываются неустойчивыми.

Здесь V * – приближённое решение,
F – функция, удовлетворяющая граничным условиям,
N m – пробные функции, которые на границе области должны быть равны нулю ,
A m – неизвестные коэффициенты, которые необходимо отыскать из условия наилучшего удовлетворения дифференциальному оператору,
M – количество пробных функций.

Если подставить V * в исходный дифференциальный оператор, то получим невязку, принимающую в различных точках области разное значение.

R = LV * + P

Здесь W n – некоторые весовые функции, в зависимости от выбора которых различают варианты метода взвешенных невязок,

S – область пространства, в которой ищется решение.

При выборе в качестве весовых функций дельта-фукций будем иметь метод, который получил название метод поточечной коллокации , для кусочно-постоянных функций – метод коллокации по подобластям, но наиболее распространенным является метод Галёркина, в котором в качестве весовых функций выбираются пробные функции N . В этом случае, если количество пробных функций равно количеству весовых функций, после раскрытия определенных интегралов приходим к замкнутой системе алгебраических уравнений относительно коэффициентов A .

KA + Q = 0

Где коэффициенты матрицы K и вектора Q вычисляются по формулам:

После нахождения коэффициентов A и подстановки их в (1), получаем решение исходной задачи.

Недостатки метода взвешенных невязок очевидны: поскольку решение ищется сразу по всей области, то количество пробных и весовых функций должно быть значительным для обеспечения приемлемой точности , но при этом возникают трудности при вычислении коэффициентов K ij и Q i , особенно при решении плоских и объемных задач, когда потребуется вычисление двойных и тройных интегралов по областям с криволинейными границами. Поэтому на практике этот метод не использовался, пока не был изобретен метод конечных элементов (МКЭ).

Кафедра физхимии ЮФУ (РГУ)

ЧИСЛЕННЫЕ МЕТОДЫ И ПРОГРАММИРОВАНИЕ

Материалы к лекционному курсу

Системы линейных уравнений

Системы n линейных уравнений с n неизвестными x 1 , x 2 , ..., x n в общем случае принято записывать следующим образом:

где а ij и b i – произвольные константы. Число n неизвестных называется порядком системы.

Решением уравнения является такая совокупность значений переменных х 1 , х 2 ,…, х n , которая одновременно обращает все уравнения системы в тождество.

Необходимым и достаточным условием существования и единственности решения системы уравнений является линейная независимость уравнений. Или, более точно, неравенство нулю определителя, составленного из коэффициентов системы уравнений:

Эквивалентной (и весьма удобной!!!) записью системы линейных уравнений является матричная запись

или сокращенно ,

в чем легко убедится, если воспользоваться правилами перемножения матриц: элемент, стоящий на пересечении i -й строки и j -го столбца матрицы-результата есть скалярное произведение i -й вектор-строки первой матрицы и j -го вектор-столбца второй матрицы.

Коэффициенты при неизвестных образуют квадратную матрицу размером n x n , (A) , переменные и свободные члены уравнений – векторы-столбцы длиной n (Х) и (В) , соответственно.

Решение системы уравнений есть вектор (X *) , который обращает это матричное уравнение в тождество.

Для решения системы линейных уравнений применяются точные методы (прямые) в которых количество арифметических, необходимых для нахождения решения, операций точно определяется порядком системы и итерационные (приближенные) методы, в которых проводится пошаговое, итерационное уточнение решения.

Оценить близость какого-либо вектора (Х) i к решению системы уравнений можно оценив близость вектора невязок, вычисляемого приведенным ниже образом, к нулевому вектору:

Для выражения меры близости в виде числа используется какая-либо норма вектора, например, Евклидова норма или длина вектора в n -мерном пространстве (другое определение – это корень квадратный из скалярного произведения вектора на себя):

Иногда используются другие векторные нормы: норма-максимум (равна наибольшей по абсолютной величине компоненте вектора)

или норма-сумма (равна сумме абсолютных величин компонентов вектора)

Обусловленность линейных алгебраических систем

Численное решение систем алгебраических уравнений является часто решаемой в рамках математического моделирования задачей. При этом как размерность задачи, так и характер матриц может существенно меняться. Вычисления, проводимые с определенной точностью, так же оказывают влияние на результат решения линейных систем. Кроме того, сами коэффициенты системы – матрица (А) и свободные члены – (В) могут быть представлены с определенной погрешностью.

Приведем такой пример:

Система уравнений

Имеет, как нетрудно убедиться подстановкой, единственное решение x = 1, y = 1.

Предположим, что при подготовке системы к решению, правая часть первого уравнения была определена с небольшой абсолютной погрешностью в +0.01, то есть, правая часть первого из уравнений вместо 11 была взята равной 11,01.

Единственным решение этой системы уравнений уже будет вектор x=11,01 y=0.

Как нетрудно убедится, в этом случае погрешность определения значений переменных оказывается существенно больше, чем погрешность коэффициента. Задачи, в которых малое изменение исходных параметров кардинально сказывается на результате называются плохо обусловленными .

Рассмотрим в общем виде систему линейных уравнений, в которой вектор свободных членов (В) представлен с некоторой абсолютной погрешностью (ΔВ) .

Если вектор (X) является точным решением уравнения с "точным" вектором (В ) .

то при наличии погрешности в правой части (ΔВ) решение системы уравнений будет отличаться от (X) на некоторый вектор (ΔX) , что можно записать следующим образом:

Раскроем скобки в правой части

И учтем точное уравнение

, умножая обе части равенства на матрицу, обратную матрице коэффициентов

Получим

т.е. абсолютная погрешность (ΔX) вычисления вектора решения (X) равна произведению матрицы, обратной матрице коэффициентов системы уравнений, на вектор абсолютной погрешности (ΔВ) .

Если перейти от матриц и векторов к соответствующим нормам, то получим, что норма вектора (ΔX) будет меньше либо равна произведению норм обратной матрицы и нормы вектора погрешности

Таким образом, если норма обратной матрицы будет велика, то абсолютная погрешность решения может быть существенно больше абсолютной погрешности правых частей уравнений системы.

Оценим, как будут при этом соотноситься относительная погрешность решения и относительной погрешностью коэффициентов. Для этого пронормируем два полученных ранее уравнения:

Перемножим отдельно левые и правые части неравенств, что, очевидно, не изменит знак неравенства и разделим обе части на и, окончательно получим:

Величина называется числом (мерой) обусловленности матрицы А . От этой величины зависит степень влияния погрешности коэффициентов системы уравнений на погрешность полученного решения. Если это число невелико, то относительная погрешность решения будет не сильно отличаться от относительной погрешности коэффициентов. Чем больше число обусловленности тем больше будет влияние погрешности коэффициентов на погрешность решения.

Аналогичный анализ можно провести и для случая наличия погрешности задания матрицы коэффициентов системы (ΔA) . И в этом случае, так же, возникает число обусловленности.

Для рассмотренного числового примера

Если взять, например, матричную норму-максимум,

, то получим

для матрицы (А) норму 1011, а для матрицы, обратной (А) - (А) -1 – 1101. Таким образом, число обусловленности оказывается равным более 1000000!

Прямые (точные) методы

Метод Гаусса и Гаусса-Жордана

Алгоритм решения заключается в приведении расширенной матрицы системы уравнений к треугольному виду (метод Гаусса) или псевдодиагональному виду (метод Гаусса-Жордана).

Метод Крамера

В данном методе (при не равенстве нулю определителя, составленного из коэффициентов системы) значения переменных определяются следующим образом

I = 1, 2, …, n

Здесь в знаменателе стоит определитель матрицы коэффициентов системы. В числителе – определитель матрицы, полученной из матрицы коэффициентов путем замены i -го столбца на вектор-столбец свободных членов системы.

Для системы, записанной в общем виде:

Метод обращения матрицы

Решение системы уравнений, записанной в матричной форме, легко найти, если воспользоваться определением обратной матрицы:

(A)(A) -1 = (A) -1 (A) = (1) ,

где (1) – единичная диагональная матрица.

Действительно,

Умножим слева обе части уравнения на обратную матрицу коэффициентов системы (A) -1

Таким образом, для решения системы, необходимо обратить матрицу коэффициентов системы и умножить полученный результат на вектор-столбец свободных членов .

Несмотря на простоту записи, метод имеет достаточную вычислительную сложность, которая заключается в нахождении обратной матрицы .

Приближенные (итерационные) методы

Метод простых итераций, метод Зейделя

Данные методы рассмотрены на примере систем нелинейных уравнений .

Метод минимальных невязок

Для решения линейных систем уравнений можно применять и различные методы поиска экстремумов. Проблема решения системы уравнений заменяется эквивалентной задачей нахождения экстремума функции n переменных.

Изучив один метод относительно подробно, переходим к изложению прочих методов целыми классами. Самым распространенным классом являются методы взвешенных невязок. Они исходят из предположения, что искомую функцию можно представить в виде функционального ряда, например такого:

Функцию f 0 обычно стараются выбирать так, чтобы она максимально точно (по возможности) удовлетворяла начальным и граничным условиям. Аппроксимирующие (пробные) функции f j предполагаются известными. Математики напридумывали некоторое количество требований к таким функциям, но их здесь обсуждать не будем. Ограничимся фактом, что полиномы и тригонометрические функции этим требованиям удовлетворяют. Еще несколько примеров наборов подобных функций будут рассмотрены при описании конкретных методов.

Коэффициенты a j заранее неизвестны, и их следует определять из системы уравнений, получаемой из исходного уравнения. От бесконечного ряда берут лишь некоторое конечное число членов.

В уравнении, которое предполагается решить, все члены переписываются в левую часть, в правой части остается лишь нуль. Таким образом, уравнение приводится к виду

Если приближенное решение (записанное в виде конечной суммы заранее выбранных функций) подставить в это уравнение, то оно не будет тождественно удовлетворяться. Следовательно, можно записать

где величина R называется невязкой. В общем случае невязка является функцией x, y, z и t. Задача сводится к нахождению таких коэффициентов a j , чтобы невязка оставалась малой во всей расчетной области. Под понятием «малой» в данных методах понимают, что интегралы по расчетной области от невязки, умноженной на некоторые весовые функции, равны нулю. То есть

Задав конечное число весовых функций, получаем систему уравнений для нахождения неизвестных коэффициентов. Задавая различные пробные аппроксимирующие (пробные) и различные весовые функции, легко получаем целый класс методов, называемый методами взвешенных невязок.

Приведем несколько примеров простейших методов из этого класса.

Метод подобластей. Расчетная область разделяется на несколько подобластей D m , могущих перекрывать друг друга. Весовую функцию задают в виде

Таким образом, обеспечивается равенство нулю интеграла от невязки по каждой подобласти. Метод послужил основой для ряда методов (один из них будет рассмотрена ниже).

Метод колокаций. В качестве весовых функций используются дельта-функция Дирака

где x= (x,y,z). Напоминаю, что функция Дирака – это хитрая функция, равная нулю везде, кроме начала координат. Но в начале она принимает неизвестное науке значение такое, что любой интеграл по области, содержащей начало координат, равен единице. Говоря проще: задаем некоторое количество точек (часто в данном подходе называемых узлами). Исходное уравнение будет удовлетворяться в этих точках. Существуют подходы к выбору этих точек и пробных функций, позволяющие максимизировать точность при ограниченном числе узлов. Но здесь их обсуждать не будем.

Метод наименьших квадратов. Метод основан на минимизации величины

Но нетрудно показать, что он тоже принадлежит к классу методов взвешенных невязок. Весовыми функциями для него являются функции вида

Пожалуй, это самый известный среди неспециалистов метод из данного класса, но далеко не самый популярный у специалистов.

Метод Галеркина. В этом методе в качестве весовых функций берутся аппроксимирующие (пробные) функции. То есть

Метод широко используется в случаях, когда хотят найти решение в виде непрерывной (а не сеточной) функции.

Рассмотрим применение этих методов к расчету деформации консольно закрепленной балки длиной L. Пусть отклонение от осевой линии описывается уравнением

Граничные условия заданы в виде

Будем искать решение в виде

Тогда невязка будет записываться в виде

Для нахождения неизвестных коэффициентов a и b нам потребуется составить систему из двух уравнений. Проделаем это всеми рассмотренными методами.

Метод колокаций. Выбираем две точки на концах балки. Приравниваем в них невязку к нулю

Получаем

Как видим, метод колокаций достаточно прост в реализации, однако уступает по точности остальным методам.

Метод подобластей. Разбиваем всю длину балки на две подобласти. В каждой из них интеграл от невязки приравниваем к нулю.

Метод Галеркина. Берем интегралы от невязки, умноженной на пробные функции.

Метод наименьших квадратов.

Метод наименьших квадратов требует наибольших вычислительных затрат, не давая при этом заметного выигрыша в точности. Поэтому он редко применяется в решении практических задач.

Тематические материалы: