.RU

Конспект лекций новосибирск 2006 содержание - 11

Шаг 6. Проверяем, достигли ли мы величины t=1. Если t<1,то переходим к шагу 4,иначе – конец.
При этом считаем, что = .
3.4. Метод дифференцирования по параметру
Здесь алгебраическая задача сводится к задаче интегрирования системы ОДУ, которая формируется следующим образом. Рассмотрим функцию как функцию параметра , т.е. обозна­чим ; Пусть непрерывно дифференцируема по t на интервале [0, 1] , тогда

Функция удовлетворяет тем же требованиям, . что и в методе продолжения решения по параметру. Следовательно, функция удовлетворяет уравнению . откуда получаем =0. Значит, из последнего соотношения имеем систему ОДУ вида
(3.14)
Система ОДУ (3.14) решается при начальных условиях t=0, x(0)= . Время меняется от 0 до 1. При t=1 получим решение системы F(x)=0 - вектор с точностью, зависящей от точности метода интегриро­вания системы (3.14). Если то по­лучим систему ОДУ

которая является нелинейной по x.
В заключение раздела следует отметить, что мы не рассматри­вали здесь довольно большую группу методов (например метод Зейделя, метод наискорейшего спуска и т.д.), которые являются тра­диционными и хорошо описаны в многочисленной литературе (напри­мер [3 - 6 ] ).
^ 4. РЕШЕНИЕ СИСТЕМ ЛИНЕЙНЫХ АУ
4.1. Метод Гаусса
Рассмотрим систему
Ax=b (4.1)
где А - неособенная матрица n*n; b,x - векторы мерности n. Для систем (4.1) с плотными матрицами не найдено алгоритмов реше­ний, для которых доказано, что они лучше по времени и точности чем метода исключения Гаусса. Гауссовское исключение существует во многих вариантах, которые алгебраически тождественны. Методы отличаются способами хранения матриц, порядком исключения, способами предупреждения больших погрешностей округления и тем, как уточняются вычисленные решения. Имеются также варианты, специаль­но приспособленные для положительно определенных матриц A.
Алгебраической основой гауссова исключения является следую­щая теорема, которую приведем без доказательства[8].
LU-теорема. Пусть дана квадратная матрица A порядка n и означает главный минор матрицы, составленный из k строк и столбцов. Предположим, что . Тогда существует единственная нижнетреугольная матрица где , и единственная верхнетреугольная матрица , такие, что LU=A. Более того
Тогда, система (4.1) может быть записана как LUx=b и сведется к двум системам о треугольными матрицами
Ly=b и Ux=y, которые легко решить.
Прямой ход Гаусса. Вычисление L и U вместе с решениям системы Ly=b обычно называется прямым ходом метода Гаус­са, имеет (n-1 ) шагов. Основная идея состоит в том, чтобы поду­чить верхнетреугольную матрицу U и пересчитать вектор b , ко­торый является решением системы Ly =b относительно y . Рассмот­рим случай n=4 .
Шаг 1. Исключаем из всех уравнений, кроме первого, . Для этого первое уравнение умножаем на и вы­читаем его последовательно из 2-го, 3-го и 4-го уравнений. Таким образом, получим три уравнения, в которых нет :
(4.2)
где , ,
При этом в преобразовании уравнения (4.1) к виду (4.2) участвова­ла матрица


Шаг 2. Исключаем из системы (4.2) Переменную . Для этого умножаем 3-е и 4-е уравнение на . Тогда умножаем и на матрицу

для получения и . В системе переменная есть только в первом уравнении, а - в первом и втором.
Шаг З. Исключение переменной . Вычисляем
и умножаем и на матрицу

и - есть верхняя треугольная матрица U, что Дает систему уравнений следующей структуры:
(4.3)
Пусть , тогда

а вектор у - есть столбец правой части в системе (4.3), который мы нашли, выполняя прямой ход Гаусса.
Обратный ход состоит в решении системы (4.3) снизу вверх: сначала находим, подставляем его в третье урав­нение и решаем его относительно и так далее до . Обрат­ный ход имеет n шагов.
Для произвольного k метод Гаусса может быть представлен следующими формулами:
Прямой ход. Здесь k - номер шага,

(4.4)

Обратный ход. Из последнего уравнения находим .
Остальные неизвестные находится последовательно по формуле
(4.5)
4.2. Способы повышения точности решении
Из соотношений (4.4) следует, что алгоритм работает, если , . Если оказалось, что какой-либо элемент, стоя­щий на главной диагонали , то вычисления нельзя продол­жать, Это неразумно и в случае, если близок к нулю. К тому же выводу приводит и анализ ошибок округления. В [8 ] показано, что для уменьшения последних величина . Для достижения этого, необходимо делать перестановки строк так, чтобы на диагонали оказывался всякий раз наибольший по абсолютной величине ко­эффициент при в результате будет выполнено требование .Такой способ часто называют методом главного элемента.
Рекомендуют иногда переставлять и столбцы, но при этом вычислительные затраты оказываются неадекватными тому выигрышу в точности, которого можно достичь.
Другим способом повышения точности является масштабирование уравнений и неизвестных. Идея метода состоит в следующем. Перемен­ные и величины правой части ; являются, как правило, реаль­ными (например, физическими) величинами, которые могут измеряться различными единицами. Если при рассмотрении коэффициентов уравне­ний мы обнаруживаем, что они на несколько порядков отличаются друг от друга разумно ввести масштабирование переменных, т.е. сделать замену одной переменной другой: , где -const
а - новая переменная. Пусть D - невырожденная диагональная матрица: Тогда x=D . Аналогично можно масштабировать вектор b с помощью матрицы . В результате получим новую систему уравнений

или окончательно после преобразований:
(4.6)
которую решают относительно .
Однако выбор нужного масштабирования очень сложен, если хо­тим получить алгоритм решения для произвольной линейной системы. В [8] приведен пример, когда при решении системы (4.6) на опреде­ленном этапе гауссова исключения новая система оказалась вырожден­ной, ввиду чего дальнейшее решение стало невозможным.
Третьим способом повышения точности решения системы линейных АУ является 2010-07-19 18:44 Читать похожую статью
  • Контрольная работа
  • Контрольная работа
  • Контрольная работа
  • Контрольная работа
  • Контрольная работа
  • Контрольная работа
  • Контрольная работа
  • Контрольная работа
  • Контрольная работа
  • Контрольная работа
  • Контрольная работа
  • Контрольная работа
  • Контрольная работа
  • Контрольная работа
  • Контрольная работа
  • Контрольная работа
  • Контрольная работа
  • Контрольная работа
  • Контрольная работа
  • Контрольная работа
  • Контрольная работа
  • Контрольная работа
  • Контрольная работа
  • Контрольная работа
  • Контрольная работа
  • Контрольная работа
  • Контрольная работа
  • Контрольная работа
  • Контрольная работа
  • Контрольная работа
  • Контрольная работа
  • Контрольная работа
  • Контрольная работа
  • Контрольная работа
  • Контрольная работа
  • Контрольная работа
  • Контрольная работа
  • Контрольная работа
  • Контрольная работа
  • Контрольная работа
  • Контрольная работа
  • Контрольная работа
  • Контрольная работа
  • Контрольная работа
  • Контрольная работа
  • Контрольная работа
  • Контрольная работа
  • Контрольная работа
  • Контрольная работа
  • Контрольная работа
  • Контрольная работа
  • Контрольная работа
  • Контрольная работа
  • Контрольная работа
  • Контрольная работа
  • Контрольная работа
  • Контрольная работа
  • Контрольная работа
  • Контрольная работа
  • Контрольная работа
  • Контрольная работа
  • Контрольная работа
  • Контрольная работа
  • Контрольная работа
  • Контрольная работа
  • Контрольная работа
  • Контрольная работа
  • Контрольная работа
  • Контрольная работа
  • Контрольная работа
  • Контрольная работа
  • Контрольная работа
  • Контрольная работа
  • Контрольная работа
  • Контрольная работа
  • Контрольная работа
  • Контрольная работа
  • Контрольная работа
  • Контрольная работа
  • Контрольная работа
  • Контрольная работа
  • Контрольная работа
  • Контрольная работа
  • Контрольная работа
  • Контрольная работа
  • Контрольная работа
  • Контрольная работа
  • Контрольная работа
  • Контрольная работа
  • Контрольная работа
  • Контрольная работа
  • Контрольная работа
  • Контрольная работа
  • Контрольная работа
  • Контрольная работа
  • Контрольная работа
  • Контрольная работа
  • Контрольная работа
  • Контрольная работа
  • Контрольная работа
  • © Помощь студентам
    Образовательные документы для студентов.