Численный анализ

📚 Краткое содержание

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

Овладейте искусством и наукой современных методов численной аппроксимации.

Автор: Ричард Л. Бёрден, Дж. Дуглас Фейрс

Благодарности: Поддержка со стороны университета Юнгстаун и вклад внесли Джон Карролл (Дублинский университет города) и различные студенческие ассистенты, включая Мария Срацича.

🎯 Цели обучения

1. Применять теорему о промежуточном значении и теорему Ролля для доказательства существования и единственности решений.
2. Конструировать полиномы Тейлора и использовать их остаточные члены для установления строгих границ погрешности численных приближений.
3. Различать округление и отбрасывание арифметики и вычислять абсолютную и относительную погрешность в системах с плавающей запятой.
4. Применять методы бисекции, неподвижной точки, Ньютона, секущих и ложного положения для приближенного нахождения корней.
5. Анализировать порядок сходимости и границы погрешности различных итерационных методов.
6. Использовать методы Айткена \Delta^2 и Стеффенсена для ускорения сходимости линейных последовательностей.
7. Формулировать и объяснять теорему Вейерштрасса об аппроксимации и её последствия для аппроксимации функций.
8. Конструировать полиномы Лагранжа, Ньютона с разделёнными разностями и Гермитовы интерполирующие полиномы для заданных наборов данных.
9. Применять метод Невилья для итеративного построения полиномиальных приближений.
10. Вывод и применение формул численного дифференцирования (трёхточечные формулы) и оценка погрешности.

🔹 Урок 1: Математические предварительные сведения и анализ ошибок

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

Цели обучения:

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

🔹 Урок 2: Решение уравнений с одной переменной

Обзор: Этот урок рассматривает численные методы нахождения нулей функции f(x) = 0, что является фундаментальной задачей в научных вычислениях. Изучаются методы, начиная от надёжного, но медленного метода бисекции до быстро сходящихся методов Ньютона и его модификаций (секущих, ложного положения). Кроме того, рассматриваются продвинутые темы, такие как анализ погрешности при итерационной сходимости, техники работы с кратными корнями, а также специализированные алгоритмы для полиномов, такие как методы Мюллера и Горнера.

Цели обучения:

• Применять методы бисекции, неподвижной точки, Ньютона, секущих и ложного положения для приближённого нахождения корней.
• Анализировать порядок сходимости и границы погрешности различных итерационных методов.
• Использовать методы Айткена \Delta^2 и Стеффенсена для ускорения сходимости линейных последовательностей.

🔹 Урок 3: Интерполяция и полиномиальная аппроксимация

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

Цели обучения:

• Формулировать и объяснять теорему Вейерштрасса об аппроксимации и её последствия для аппроксимации функций.
• Конструировать полиномы Лагранжа, полиномы Ньютона с разделёнными разностями и интерполирующие полиномы Эрмита для заданных наборов данных.
• Применять метод Невилья для итеративного построения полиномиальных приближений.

🔹 Урок 4: Численное дифференцирование и интегрирование

Обзор: Этот урок охватывает численную аппроксимацию производных и интегралов, что необходимо для решения математических задач, где аналитические решения трудно или невозможно получить. Учащиеся исследуют высокоточные методы дифференцирования с использованием трёхточечных формул и экстраполяции Ричардсона, проходят через методы Ньютона-Котса (правило трапеций и правило Симпсона) и осваивают продвинутые методы квадратур, включая Ромберг, адаптивные и гауссовы методы. Завершает курс численная обработка двойных интегралов и несобственных интегралов.

Цели обучения:

• Вывод и применение формул численного дифференцирования (трёхточечные формулы) и оценка погрешности.
• Реализация экстраполяции Ричардсона для повышения точности численных приближений.
• Применение композитных правил численного интегрирования и адаптивной квадратуры для обработки сложных вариаций функций.

🔹 Урок 5: Задачи с начальными условиями для обыкновенных дифференциальных уравнений

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

Цели обучения:

• Определять, является ли ЗНУ хорошо поставленной, используя условие Липшица и теоремы существования-единственности.
• Реализовывать и анализировать погрешность одноступенчатых методов (Эйлера, Тейлора, Рунге-Кутты) и многошаговых методов (Адамса-Башфорта, Адамса-Мултона).
• Применять адаптивные техники (Рунге-Кутта-Фельберга, переменный шаг) и экстраполяцию для решения ОДУ в заданных пределах погрешности.

🔹 Урок 6: Прямые методы решения систем линейных уравнений

Обзор: Этот урок охватывает систематические алгоритмические подходы к решению систем линейных уравнений, переходя от базовой методики Гаусса к продвинутым техникам матричной факторизации. Учащиеся изучают стратегии поддержания численной устойчивости с помощью перестановки, анализируют алгебраические свойства матриц (обращение, определители) и реализуют специализированные факторизации (LU, LDL^t, Холеский, Круа), обеспечивающие эффективные вычисления в инженерных и научных контекстах.

Цели обучения:

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

🔹 Урок 7: Итерационные методы в матричной алгебре

Обзор: Этот урок охватывает переход от прямых к итерационным методам решения больших систем линейных уравнений. Фокусируется на измерении величины векторов и матриц с помощью норм, определении критериев сходимости через спектральный радиус, а также реализации основных итерационных алгоритмов, включая Якоби, Гаусса-Зейделя и последовательного перераспределения (SOR). Кроме того, рассматриваются вопросы численной устойчивости через итерационную корректировку, границы погрешности и высокоэффективный метод сопряжённых градиентов, улучшенный с помощью предобусловливания.

Цели обучения:

• Вычислять нормы векторов и матриц (l_2 и l_\infty) и определять спектральный радиус матрицы для оценки сходимости.
• Реализовывать и сравнивать итерационные методы Якоби, Гаусса-Зейделя и SOR для решения системы A\mathbf{x} = \mathbf{b}.
• Оценивать границы погрешности с помощью числа обусловленности и применять итерационную корректировку для повышения точности приближённых решений.

🔹 Урок 8: Теория аппроксимации

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

Цели обучения:

• Конструировать и решать нормальные уравнения для дискретной линейной и полиномиальной аппроксимации наименьших квадратов.
• Создавать ортогональные базисы полиномов с помощью процесса Грама-Шмидта для избежания плохо обусловленных систем.
• Применять полиномы Чебышёва для минимизации максимальной погрешности интерполяции и выполнять экономию полиномов.

🔹 Урок 9: Приближение собственных значений

Обзор: Этот урок сосредоточен на численных методах приближения собственных значений, выходя за рамки символических корней характеристических полиномов, которые часто являются вычислительно затратными или невозможными для больших матриц. Учащиеся научатся локализовать собственные значения с помощью теоремы Гершгорина, применять итерационные методы, такие как метод силы и обратный метод силы, для нахождения доминирующих и конкретных собственных значений, а также использовать структурные преобразования (метод Хаусхолдера и алгоритм QR) и разложение по сингулярным значениям (SVD) для всестороннего анализа матриц.

Цели обучения:

• Локализовать собственные значения в комплексной плоскости с помощью теоремы Гершгорина.
• Реализовать метод силы и обратный метод силы с ускорением Айткена для нахождения доминирующих и смещённых собственных значений.
• Привести симметричные матрицы к трёхдиагональной форме с помощью метода Хаусхолдера и найти все собственные значения с помощью алгоритма QR.

🔹 Урок 10: Численные решения систем нелинейных уравнений

Обзор: Этот урок охватывает переход от поиска корней одной переменной к решению систем нелинейных уравнений, где главная цель — найти вектор \mathbf{x} такой, что \mathbf{F}(\mathbf{x}) = \mathbf{0}. Исследуются итерации неподвижной точки для нескольких переменных, метод Ньютона, основанный на якобиане, вычислительно эффективные квазиньютоновские методы (в частности, метод Бройдена), а также устойчивые техники, такие как метод наискорейшего спуска и гомотопия/продолжение, для нахождения начальных приближений или обработки систем, где стандартные методы не работают.

Цели обучения:

• Определять и применять итерацию неподвижной точки для функций нескольких переменных и определять критерии сходимости с помощью теоремы 10.6.
• Строить якобиан для нелинейной системы и реализовывать метод Ньютона для достижения квадратичной сходимости.
• Выполнять метод Бройдена с использованием формулы Шермана-Моррисона для эффективного обновления обратной матрицы Якоби.

🔹 Урок 11: Задачи с граничными условиями для обыкновенных дифференциальных уравнений

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

Цели обучения:

• Применять теорему 11.1 для определения существования и единственности решений задач с граничными условиями.
• Преобразовать задачу второго порядка с граничными условиями в пару задач с начальными условиями (ЗНУ) с помощью метода линейной стрельбы.
• Реализовывать метод Ньютона для итеративного решения нелинейных задач стрельбы.

🔹 Урок 12: Численные решения уравнений в частных производных

Обзор: Этот урок охватывает численную аппроксимацию решений трёх основных классов уравнений в частных производных (УЧП): эллиптических, параболических и гиперболических. С помощью метода конечных разностей учащиеся учатся дискретизировать непрерывные области в сеточные структуры и преобразовывать дифференциальные операторы в алгебраические системы уравнений. Основное внимание уделяется устойчивости временных методов (прямые разности против Кранка-Николсона) и итерационному решению стационарных систем (уравнения Пуассона и Лапласа).

Цели обучения:

• Дискретизировать пространственные и временные области с помощью сеток конечных разностей для различных типов УЧП.
• Применять методы прямых разностей, обратных разностей и Кранка-Николсона для решения параболических уравнений теплопроводности с учётом условий устойчивости.
• Строить и решать линейные системы, полученные из эллиптических уравнений (Пуассона/Лапласа) и гиперболических волновых уравнений.