Научная библиотека
Клуб читателей
Вычисления в дробях
Информационный ассистент
sc_lib@list.ru

Поиск в библиотеке:
Научная библиотека
избранных естественно-научных изданий
научная-библиотека.рф
Логин:
Пароль:
Регистрация
или

<< Предыдущий параграфСледующий параграф >>

< Назад
Далее >

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

< Назад
Далее >
<< Предыдущий параграфСледующий параграф >>

Макеты страниц

§ 1. Методы последовательного исключения неизвестных

Рассмотрим точные методы решения системы ; здесь — матрица размерности

Метод решения задачи относят к классу точных, если в предположении отсутствия округлений он дает точное решение задачи после конечного числа арифметических и логических операций. Если число ненулевых элементов матрицы системы имеет порядок , то для большинства используемых в настоящее время точных методов решения таких систем требуемое число операций имеет порядок . Поэтому для применимости точных методов необходимо, чтобы такой порядок числа операций был приемлем для данной ЭВМ; другие ограничения накладываются объемом и структурой памяти ЭВМ.

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

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

делим на коэффициент , в результате получаем уравнение

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

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

Совокупность проведенных вычислений, в ходе которых исходная задача преобразовалась к виду (2), называется прямым ходом метода Гаусса.

Из уравнения системы (2) определяем , из и т. д. до . Совокупность таких вычислений называют обратным ходом метода Гаусса.

Нетрудно проверить, что реализация прямого хода метода Гаусса требует арифметических операций, а обратного — арифметических операций.

Исключение происходит в результате следующих операций: 1) деления уравнения на , 2) вычитания получающегося после такого деления уравнения, умноженного на , из уравнений с номерами к . Первая операция равносильна умножению системы уравнений слева на диагональную матрицу

вторая операция равносильна умножению слева на матрицу

Таким образом, система (2), получаемая в результате этих преобразований, запишется в виде

Произведение левых (правых) треугольных матриц является левой (правой) треугольной матрицей, поэтому матрица С левая треугольная. Из формулы для элементов обратной матрицы

следует, что матрица, обратная к левой (правой) треугольной, является левой (правой) треугольной. Следовательно, матрица левая треугольная.

Введем обозначение . Согласно построению все и матрица D правая треугольная. Отсюда получаем представление матрицы А в виде произведения левой и правой треугольных матриц:

Равенство вместе с условием , образует систему уравнений относительно элементов треугольных матриц В и : . Поскольку при и при , эта система может быть записана в виде

(3)

или, что то же самое,

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

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

Таким образом, вместо последовательных преобразований системы (1) к виду (2) можно непосредственно произвести вычисление матриц В и с помощью формул (4). Эти вычисления можно осуществить, если только все элементы окажутся отличными от нуля. Пусть — матрицы главных миноров порядка матриц А, В, D. Согласно (3) . Поскольку , то . Следовательно,

Итак, для осуществления вычислений по формулам (4) необходимо и достаточно выполнение условий

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

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

Последовательность операций по разложению матрицы А на произведение треугольных матриц и по определению вектора d часто удобно объединить. Уравнения

системы можно записать в виде

Следовательно, значения могут вычисляться одновременно с остальными значениями по формулам (4).

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

Обычно эти матрицы имеют так называемую ленточную структуру. Более точно, матрицу А называют -диагональной или имеющей ленточную структуру, если при . Число называют шириной ленты. Оказывается, что при решении системы уравнений с ленточной матрицей методом Гаусса число арифметических операций и требуемый объем памяти ЭВМ могут быть существенно сокращены.

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

Задача 2. Оценить объем загружаемой памяти ЭВМ в методе Гаусса для ленточных матриц.

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

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

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

Обратный ход метода Гаусса также сопровождается вычислением контрольных элементов строк системы.

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

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

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

Часто требуется решить несколько систем уравнений , с одной и той же матрицей А. Удобно поступить следующим образом: введя обозначения

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

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

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

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

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

Наряду с исходной системой тем же методом решается система

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

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

Для решения таких систем, а также систем уравнений более общего вида с эрмитовой не обязательно положительно определенной матрицей применяется метод квадратного корня (метод Холецкого). Матрица А представляется в виде

где S — правая треугольная матрица, — сопряженная с ней, т. е.

причем все — диагональная матрица с элементами , равными или —1. Матричное равенство (6) образует систему уравнений

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

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

Задача 3. Оценить число арифметических операций и загрузку памяти ЭВМ (при условии объем памяти, требуемый для запоминания матрицы А, уменьшается) при решении системы с вещественной положительно определеннной матрицей А методом квадратного корня.

Многие пакеты прикладных программ для решения краевых задач математической физики методом конечных элементов организованы по следующей схеме. После формирования матрицы системы А путем перестановки строк и столбцов (одновременно переставляются и строки и и столбцы) система преобразуется к виду с наименьшей шириной ленты. Далее применяется метод квадратного корня. При этом с целью уменьшения объема вычислений при решении системы с другими правыми частями матрица S запоминается.

Замечание. Часто этот метод уступает по эффективности итерационным методам.

Задача 4. Оценить число арифметических операций и объем требуемой памяти метода квадратного корня в случае матриц ленточной структуры.

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

Решая эту систему в условиях реальных округлений, получаем приближение к . Полагаем . Если точность нового приближения представляется неудовлетворительной, то повторяем эту операцию. При решении системы (7) над компонентами правой части производятся те же линейные операции, что и над компонентами правой части при решении системы (1). Поэтому при вычислениях на ЭВМ с плавающей запятой естественно ожидать, что относительные погрешности решений этих систем будут одного порядка. Поскольку погрешности округлений обычно малы, то тогда , и, как правило, решение (7) определится с существенно меньшей абсолютной погрешностью, чем решение системы (1). Таким образом, применение приема приводит к повышению точности приближенного решения.

Особенно удобно применять этот прием, когда по ходу вычислений в памяти ЭВМ сохраняются матрицы В и D. Тогда для каждого уточнения требуется найти вектор и решить две системы с треугольными матрицами. Это потребует всего арифметических операций, что составит малую долю от числа операций , требующихся для представления матрицы А в виде .

Идея описанного приема последовательного уточнения приближений к решению часто реализуется в такой форме.

Пусть матрица В близка в каком-то смысле к матрице А, но решение системы требует существенно меньшего объема вычислений по сравнению с решением системы . Решение системы принимаем в качестве первого приближения к решению. Разность удовлетворяет системе уравнений

Вместо решения этой системы находим решение системы

и полагаем . Таким образом, каждое приближение находится из предыдущего по формуле

Если матрицы А и В достаточно близки, то матрица имеет малую норму и такой итерационный процесс быстро сходится (см. также § 10).

Значительно более редкой, чем задача решения системы уравнений, является задача обращения матриц. Для обратной матрицы имеем равенство . Таким образом, для нахождения матрицы X достаточно последовательно решить две матричные системы , . Нетрудно подсчитать, что при нахождении на таком пути матрицы общий объем вычислений составит арифметических операций.

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

Отсюда получаем цепочку равенств

Поскольку

то имеем оценку

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

<< Предыдущий параграфСледующий параграф >>

Оглавление

Предисловие
Введение
Глава 1. Погрешность результата численного решения задачи
§ 1. Источники и классификация погрешности
§ 2. Запись чисел в ЭВМ
§ 3. Абсолютная и относительная погрешности. Формы записи данных
§ 4. О вычислительной погрешности
§ 5. Погрешность функции
§ 6. Обратная задача
Глава 2. Интерполяция и численное дифференцирование
§ 1. Постановка задачи приближения функций
§ 2. Интерполяционный многочлен Лагранжа
§ 3. Оценка остаточного члена интерполяционного многочлена Лагранжа
§ 4. Разделенные разности и их свойства

§ 5. Интерполяционная формула Ньютона с разделенными разностями
§ 6. Разделенные разности и интерполирование с кратными узлами
§ 7. Уравнения в конечных разностях
§ 8. Многочлены Чебышева
§ 9. Минимизация оценки остаточного члена интерполяционной формулы
§ 10. Конечные разности
§ 11. Интерполяционные формулы для таблиц с постоянным шагом
§ 12. Составление таблиц
§ 13. О погрешности округления при интерполяции
§ 14. Применения аппарата интерполирования. Обратная интерполяция
§ 15. Численное дифференцирование
§ 16. О вычислительной погрешности формул численного дифференцирования
§ 17. Рациональная интерполяция
Глава 3. Численное интегрирование
§ 1. Простейшие квадратурные формулы. Метод неопределенных коэффициентов
§ 2. Оценки погрешности квадратуры
§ 3. Квадратурные формулы Ньютона—Котеса
§ 4. Ортогональные многочлены
§ 5. Квадратурные формулы Гаусса
§ 6. Практическая оценка погрешности элементарных квадратурных формул
§ 7. Интегрирование быстро осциллирующих функций
§ 8. Повышение точности интегрирования за счет разбиения отрезка на равные части
§ 9. О постановках задач оптимизации
§ 10. Постановка задачи оптимизации квадратур
§11. Оптимизация распределения узлов квадратурной формулы
§ 12. Примеры оптимизации распределения узлов
§ 13. Главный член погрешности
§ 14. Правило Рунге практической оценки погрешности
§ 15. Уточнение результата интерполяцией более высокого порядка точности
§ 16. Вычисление интегралов в нерегулярном случае
§ 17. Принципы построения стандартных программ с автоматическим выбором шага
Глава 4. Приближение функций и смежные вопросы
§ 1. Наилучшие приближения в линейном нормированном пространстве
§ 2. Наилучшее приближение в гильбертовом пространстве и вопросы, возникающие при его практическом построении
§ 3. Тригонометрическая интерполяция. Дискретное преобразование Фурье
§ 4. Быстрое преобразование Фурье
§ 5. Наилучшее равномерное приближение
§ 6. Примеры наилучшего равномерного приближения
§ 7. О форме записи многочлена
§ 8. Интерполяция и приближение сплайнами
Глава 5. Многомерные задачи
§ 1. Метод неопределенных коэффициентов
§ 2. Метод наименьших квадратов и регуляризация
§ 3. Примеры регуляризации
§ 4. Сведение многомерных задач к одномерным
§ 5. Интерполяция функций в треугольнике
§ 6. Оценка погрешности численного интегрирования на равномерной сетке
§ 7. Оценка снизу погрешности численного интегрирования
§ 8. Метод Монте-Карло
§ 9. Обсуждение правомерности использования недетерминированных методов решения задач
§ 10. Ускорение сходимости метода Монте-Карло
§ 11. О выборе метода решения задачи
Глава 6. Численные методы алгебры
§ 1. Методы последовательного исключения неизвестных
§ 2. Метод отражений
§ 3. Метод простой итерации
§ 4. Особенности реализации метода простой итерации на ЭВМ
§ 5. Процесс практической оценки погрешности и ускорения сходимости
§ 6. Оптимизация скорости сходимости итерационных процессов
§ 7. Метод Зейделя
§ 8. Метод наискорейшего градиентного спуска
§ 9. Метод сопряженных градиентов
§ 10. Итерационные методы с использованием спектрально-эквивалентных операторов
§ 11. Погрешность приближенного решения системы уравнений и обусловленность матриц. Регуляризация
§ 12. Проблема собственных значений
§ 13. Решение полной проблемы собственных значений при помощи QR-алгоритма
Литература
Глава 7. Решение систем нелинейных уравнений и задач оптимизации
§ 1. Метод простой итерации и смежные вопросы
§ 2. Метод Ньютона решения нелинейных уравнений
§ 3. Методы спуска
§ 4. Другие методы сведения многомерных задач к задачам меньшей размерности
§ 5. Решение стационарных задач путем установления
§ 6. Как оптимизировать?
Глава 8. Численные методы решения задачи Коши для обыкновенных дифференциальных уравнений
§ 1. Решение задачи Коши с помощью формулы Тейлора
§ 2. Методы Рунге—Кутта
§ 3. Методы с контролем погрешности на шаге
§ 4. Оценки погрешности одношаговых методов
§ 5. Конечно-разностные методы
§ 6. Метод неопределенных коэффициентов
§ 7. Исследование свойств конечно-разностных методов на модельных задачах
§ 8. Оценка погрешности конечно-разностных методов
§ 9. Особенности интегрирования систем уравнений
§ 10. Методы численного интегрирования уравнений второго порядка
§ 11. Оптимизация распределения узлов интегрирования
Глава 9. Численные методы решения краевых задач для обыкновенных дифференциальных уравнений
§ 1. Простейшие методы решения краевой задачи для уравнений второго порядка
§ 2. Функция Грина сеточной краевой задачи
§ 3. Решение простейшей краевой сеточной задачи
§ 4. Замыкания вычислительных алгоритмов
§ 5. Обсуждение постановок краевых задач для линейных систем первого порядка
§ 6. Алгоритмы решения краевых задач для систем уравнений первого порядка
§ 7. Нелинейные краевые задачи
§ 8. Аппроксимации специального типа
§ 9. Конечно-разностные методы отыскания собственных значений
§ 10. Построение численных методов с помощью вариационных принципов
§ 11. Улучшение сходимости вариационных методов в нерегулярном случае
§ 12. Влияние вычислительной погрешности в зависимости от формы записи конечно-разностного уравнения
Глава 10. Методы решения уравнений в частных производных
§ 1. Основные понятия теории метода сеток
§ 2. Аппроксимация простейших гиперболических задач
§ 3. Принцип замороженных коэффициентов
§ 4. Численное решение нелинейных задач с разрывными решениями
§ 5. Разностные схемы для одномерного параболического уравнения
§ 6. Разностная аппроксимация эллиптических уравнений
§ 7. Решение параболических уравнений с несколькими пространственными переменными
§ 8. Методы решения сеточных эллиптических уравнений
Литература
Глава 11. Численные методы решения интегральных уравнений
§ 1. Решение интегральных уравнений методом замены интеграла квадратурной суммой
§ 2. Решение интегральных уравнений с помощью замены ядра на вырожденное
§ 3. Интегральные уравнения Фредгольма первого рода
Заключение
Список литературы

© Научная библиотека