Обзор численных методов
Численные методы это увлекательное и чрезвычайно важное направление современной математики, связанное с вычислениями на компьютере и решением сложных задач.
Чистая математика изучает движение чисел — арифметика, движение фигур – геометрия, но как числа соединяются с реальным миром? Как от формул перейти к окружающему нас миру?
Ответ на это дают численные методы, математика, соединенная с силой компьютера, позволяет заглянуть вглубь реального мира, промоделировать сложнейшие физические, технические и биологические процессы.
Наблюдая процессы реального мира, мы вначале описываем их вербально, пытаясь понять суть явлений, далее строим математические модели.
Однако, мы не хотим ограничиваться построением формальных моделей, а хотим получить качественное и количественное представление об изучаемых процессах, увидеть их на графиках.
Именно здесь нам на помощь приходят компьютеры и численные методы.
Представьте, нам требуется исследовать какой-либо сложный физический или биологический процесс, например, понять законы кровообращения или движения газа в жидкостях.
Мы можем вербально описать эти процессы, выделить главные закономерности, сформулировать основные законы, которым подчиняется данный процесс. Это вербальная или словесная, логическая модель.
Затем мы пытаемся выразить эти законы в виде математических уравнений, например, дифференциальных или интегральных уравнений, но чтобы познать процесс, мы должны идти дальше и решить эти уравнения.
Что понимается под словом решить? Здесь начинается волшебство. Компьютер позволит нам увидеть тот же процесс, но в виде чисел. Этот удивительный момент требует серьезного рассмотрения.
Большинство реальных процессов описывается нелинейными уравнениями, которые лишь в первом приближении можно заменить линейными.
Возникает вопрос: как решать эти уравнения, какова точность решения, вот здесь и вступают в свои права численные методы.
Только в исключительных случаях математические уравнения, описывающие реальные процессы, можно решить в явном виде. Иногда говорят, что доказано существование и единственность решения, но где это решение в явном виде, каковы его свойства, что мы можем сказать о поведении этого процесса через определенное время и в определенных условиях.
Нам нужно получить это решение в явном виде, если это молекулярный процесс, то вплоть до поведения отдельных молекул.
Именно это и есть передовые рубежи современного естествознания.
В известном смысле удивительно, что странные манипуляции компьютера приводят к потрясающим выводам, позволяют заглянуть вглубь природы, именно здесь проявляется сила компьютеров, творящих новую действительность и моделирующих природу.
Замечательно, что есть математические принципы нахождения компьютерных решений с заданной точностью.
Под численными методами в широком смысле можно понимать интерпретацию математической модели на языке, доступном компьютеру.
Например, если математическая модель представлены в виде дифференциального уравнения, то численным методом может быть разностное уравнение, приближающее исходное дифференциальное.
Для того чтобы использовать компьютер, мы должны составить программу, реализующую данный численный метод.
Самое замечательное то, что используя компьютер, мы находим свойства процесса, о которых ранее могли только догадываться.
Итак, основу вычислительного эксперимента составляет триада: математическая модель – метод и алгоритм решения – компьютерная программа.
Каждый член этой триады важен и без него нельзя провести по-настоящему глубокого исследования.
В чем состоит искусство?
Одной и той же модели можно сопоставить множество разнообразных дискретных моделей, однако не все они подходят для практического использования.
Вычислительные алгоритмы должны удовлетворять определенным требованиям. Дискретная модель должна быть комплементарна компьютеру.
Можно выделить две группы требований к вычислительным алгоритмам: адекватность исходной задаче и эффективная компьютерная реализуемость.
Адекватность включает в себя сходимость метода, выполнение математических аналогов законов сохранения, качественно правильное поведение метода, его соответствие модели.
Численный метод сходится, если при увеличении числа уравнений решение дискретной задачи стремится к решению исходной задачи.
Заметим, что компьютер оперирует лишь с конечным числом уравнений, поэтому необходимо оценивать погрешность дискретной модели в зависимости от числа уравнений.
Искусство состоит в том, чтобы построить дискретную модель небольшой размерности, вполне адекватную исходной задаче.
Предположим, мы имеем обыкновенные дифференциальные уравнения или уравнения в частных производных.
Вначале мы дискретизируем задачу, заменяя область изменения аргумента дискретным множеством точек или сеткой, непрерывное время также заменяется дискретными моментами, далее мы аппроксимируем производные и переходим к конечно-разностным отношениям.
В результате мы получаем приближенное описание реального процесса системой алгебраических уравнений. Известно, что дифференциальные уравнения, описывающие физические процессы, являются следствиями законов сохранения, поэтому разумно требовать, чтобы для разностных схем также выполнялись законы сохранения.
Такие схемы называются консервативными, именно они наиболее адекватно отражают поведение решения исходной задачи.
Корректность численного метода должна соответствовать корректности исходной задачи, иными словами, однозначной разрешимости и непрерывной зависимости от исходных данных.
Компьютерная реализация метода включает требования по памяти и времени, метод должен быть реализуем за определенное время на данном компьютере с учетом его быстродействия и памяти.
Материал данного раздела располагается в такой последовательности: решение систем линейных уравнений, решение нелинейных уравнений, решение систем нелинейных уравнений, решение дифференциальных уравнений, методы интерполяции.
Мы стараемся максимально популярно изложить материал и надеемся, что он будет с интересом воспринят физиками, биологами, инженерами, врачами, всеми людьми, интересующимися современной компьютерной аналитикой.
В начало
Содержание портала
Численные методы | ИКФИА СО РАН
Алберг Дж., Нильсон В., Уолш Дж. Теория сплайнов и ее приложения. М.: Мир, 1972 (pdf)
Бабенко К.И. (ред.). Теоретические основы и конструирование численных алгоритмов задач математической физики. М.: Наука, 1979 (pdf)
Бабушка И., Витасек Э., Прагер М. Численные процессы решения дифференциальных уравнений. М.: Мир, 1969 (pdf)
Бахвалов Н.С. Численные методы (анализ, алгебра, обыкновенные дифференциальные уравнения). М.: Наука, 1975 (pdf)
Березин И.С., Жидков Н.П. Методы вычислений, том 1 (2-е изд.). М.: Физматлит, 1962 (pdf)
Березин И.С., Жидков Н.П. Методы вычислений, том 2. М.: Физматлит, 1959 (pdf)
Витушкин А.Г. Оценка сложности задачи табулирования. М.: ГИФМЛ, 1959 (pdf)
Ворожцов Е.В. Разностные методы решения задач механики сплошных сред (учебное пособие). Новосибирск: НГТУ, 1998 (pdf)
Ворожцов Е.В., Яненко Н.Н. Методы локализации особенностей в вычислительной газодинамике. Новосибирск: Наука, 1985 (pdf)
Гавурин М.К. Лекции по методам вычислений. М.: Наука, 1971 (pdf)
Гельфонд О. Исчисление конечных разностей. М.: ГИФМЛ, 1959 (pdf)
Гловински Р., Лионс Ж.-Л., Тремольер Р. Численное исследование вариационных неравенств. М.: Мир, 1979 (pdf)
Годунов С.К., Забродин А.В., Иванов М.Я., Крайко А.Н., Прокопов Г.П. Численное решение многомерных задач газовой динамики. М.: Наука, 1976 (pdf)
Деклу Ж. Метод конечных элементов. М.: Мир, 1976 (pdf)
Демидович Б.П., Марон И.А. Основы вычислительной математики (3-е изд.). М.: Наука, 1966 (pdf)
Демидович Б.П., Марон И.А., Шувалова Э.З. Численные методы анализа. Приближение функций, дифференциальные и интегральные уравнения. М.: Наука, 1967 (pdf)
Дзядык В.К. Введение в теорию равномерного приближения функций полиномами. М.: Наука, 1977 (pdf)
Дородницын А.А. Численные методы решения дифференциальных и интегральных уравнений и квадратурные формулы. Сборник статей. М.: Наука, 1964 (pdf)
Дьяченко В.Ф. Основные понятия вычислительной математики. М.: Наука, 1972 (pdf)
Зенкевич О. Метод конечных элементов в технике. М.: Мир, 1975 (pdf)
Калиткин Н.Н. Численные методы. М.: Наука, 1978 (pdf)
Канторович Л.В., Крылов В.И. Приближенные методы высшего анализа (5-е изд.). М.-Л.: Физматлит, 1962 (pdf)
Коллатц Л. Задачи на собственные значения (с техническими приложениями). М.: Наука, 1968 (pdf)
Коллатц Л. Функциональный анализ и вычислительная математика. М.: Мир, 1969 (pdf)
Коллатц Л., Альбрехт Ю. Задачи по прикладной математике. М.: Мир, 1978 (pdf)
Коннор Дж., Бреббиа К. Метод конечных элементов в механике жидкости. Л.: Судостроение, 1979 (pdf)
Корнейчук Н.П. Экстремальные задачи теории приближения. М.: Наука, 1976 (pdf)
Крылов В.И. Приближенное вычисление интегралов (2-е изд.). М.: Наука, 1967 (pdf)
Крылов В.И., Бобков В.В., Mонастырный П.И. Вычислительные методы. Том II. М.: Наука, 1977 (pdf)
Кунцман Ж. Численные методы. М.: Наука, 1979 (pdf)
Ланцош К. Практические методы прикладного анализа. Справочное руководство. М.: ГИФМЛ, 1961 (pdf)
Латтес Р. , Лионс Ж.-Л. Метод квазиобращения и его приложения. М.: Мир, 1970 (pdf)
Лифанов И.К. Метод сингулярных интегральных уравнений и численный эксперимент. М.: ТОО Янус, 1995 (pdf)
Лоран П.-Ж. Аппроксимация и оптимизация. М.: Мир, 1975 (pdf)
Мак-Кракен Д., Дорн У. Численные методы и программирование на ФОРТРАНе. М.: Мир, 1969 (pdf)
Марчук Г.И. Методы вычислительной математики. М.: Наука, 1977 (pdf)
Медведев Н.В. Применение сплайнов в теории приближений. Чебоксары: ЧГУ, 1977 (pdf)
Михлин С.Г., Смолицкий X.Л. Приближенные методы решения дифференциальных и интегральных уравнений. М.: Наука, 1965 (pdf)
Оден Дж. Конечные элементы в нелинейной механике сплошных сред. М.: Мир, 1976 (pdf)
Ортега Дж., Рейнболдт В. Итерационные методы решения нелинейных систем уравнений со многими неизвестными. М.: Мир, 1975 (pdf)
Островский А.М. Решение уравнений и систем уравнений. М.: ИЛ, 1963 (pdf)
Полежаев В.И., Бунэ А.В., Верезуб Н.А. и др. Математическое моделирование конвективного тепломассообмена на основе уравнений Навье — Стокса. М.: Наука, 1987 (pdf)
Поттер Д. Вычислительные методы в физике. М.: Мир, 1975 (pdf)
Рихтмайер Р., Мортон К. Разностные методы решения краевых задач. М.: Мир, 1972 (pdf)
Рутисхаузер Г. Алгоритм частных и разностей. М.: ИЛ, 1960 (pdf)
Самарский А.А. Введение в теорию разностных схем. М.: Наука, 1971 (pdf)
Самарский А.А., Николаев Е.С. Методы решения сеточных уравнений. М.: Наука, 1978 (pdf)
Сегерлинд Л. Применение метода конечных элементов. М.: Мир, 1979 (pdf)
Соболь И.М. Численные методы Монте-Карло. М.: Наука, 1973 (pdf)
Стренг Г., Фикс Дж. Теория метода конечных элементов. М.: Мир, 1977 (pdf)
Форсайт Дж., Молер К. Численное решение систем линейных алгебраических уравнений. М.: Мир, 1969 (pdf)
Хемминг Р.В. Численные методы (2-е изд.). М.: Наука, 1972 (pdf)
Черноусько Ф.Л., Баничук Н.В. Вариационные задачи механики и управления (Численные методы). М.: Наука, 1973 (pdf)
Штеттер X. Анализ методов дискретизации для обыкновенных дифференциальных уравнений. М.: Мир, 1978 (pdf)
Учебный план | Введение в численные методы | Математика
Время проведения занятий
Лекции: 3 занятия/неделю, 1 час/занятие
Предпосылки
18.06 Линейная алгебра , 18.700 Линейная алгебра или эквивалент
Описание
Этот курс представляет собой расширенное введение в числовую линейную алгебру и связанные с ней численные методы. Темы включают прямые и итерационные методы для линейных систем, разложения по собственным значениям и факторизации QR / SVD, стабильность и точность численных алгоритмов, стандарт IEEE с плавающей запятой, разреженные и структурированные матрицы и программное обеспечение для линейной алгебры. Другие темы могут включать иерархии памяти и влияние кэшей на алгоритмы, нелинейную оптимизацию, численное интегрирование, БПФ и анализ чувствительности. Наборы задач будут включать использование Julia, среды, похожей на MATLAB® (не требуется никакого предварительного опыта; вы будете учиться по ходу дела).
Обязательный учебник
Трефетен, Ллойд Н. и Дэвид Бау III.
Дополнительные показания
Барретт, Ричард, Майкл Берри и др. Шаблоны для решения линейных систем: строительные блоки для итерационных методов . SIAM: Общество промышленной и прикладной математики, 1987. ISBN: 9780898713282.
Бай, Чжаоцзюнь, Джеймс Деммель и др. Шаблоны для решения алгебраических задач на собственные значения: практическое руководство . SIAM: Общество промышленной и прикладной математики, 1987. ISBN: 9780898714715.
Требования к курсу
Включает четыре набора задач, промежуточный экзамен на дом и финальный проект.
Политики сотрудничества
Говорите с кем хотите и читайте все, что хотите, за тремя исключениями: во-первых, вы не можете ссылаться на решения домашних заданий из предыдущих условий. Во-вторых, постарайтесь решить проблему самостоятельно, прежде чем обсуждать ее с одноклассниками или гуглить. В-третьих, независимо от того, с кем вы разговариваете или что читаете, запишите решение самостоятельно, не имея перед собой их ответа.
Финальный проект
Окончательный проект будет состоять из 8–15 страниц (в одну колонку, через один интервал, в идеале с использованием шаблона стиля из SIAM Journal on Numerical Analysis ), в котором будет рассмотрен интересный численный алгоритм, не рассмотренный в курсе. [Поскольку это не численный курс дифференциальных уравнений с частными производными, алгоритм не должен быть алгоритмом превращения УЧП в конечные/дискретизированные системы; однако ваш проект может использовать дискретизацию PDE как заданный «черный ящик» и рассматривать некоторые другие аспекты проблемы, например. итеративные решатели.] Ваша статья должна быть написана для аудитории ваших сверстников в классе и должна включать пример числовых результатов (ваших) от приложения к реалистичной задаче (мелкий масштаб в порядке), обсуждение характеристик точности и производительности ( как теоретический, так и экспериментальный), и справедливое сравнение по крайней мере с одним конкурирующим алгоритмом для той же задачи.
Часто задаваемые вопросы о финальном проекте:
- Это должно быть о численной линейной алгебре? Нет. Это может быть любая числовая тема (в основном, все, где вы вычисляете концептуально реальный результат, а не целочисленные вычисления), за исключением алгоритмов дискретизации УЧП.
- Можно ли использовать матрицу из дискретизированного УЧП? Да. Вы можете взять матрицу из PDE в качестве входных данных, а затем обсудить итерационные методы ее решения и так далее. Я просто не хочу, чтобы статья была посвящена самой технике дискретизации УЧП.
- Насколько официально предложение? Очень неформально — одна страница с описанием того, что вы планируете делать, с парой ссылок, которые вы используете в качестве отправной точки. По сути, это предложение просто для того, чтобы я мог убедиться, что то, что вы планируете, разумно, и дать вам предварительный отзыв.
- Сколько кода мне нужно написать?
- Как я должен сравнивать производительность? Будьте очень осторожны при измерении времени: если вы не измеряете высокооптимизированный код или не заботитесь только о порядках величины, измерения времени больше касаются качества реализации, чем алгоритмов. Лучше измерять что-то, не зависящее от реализации (например, подсчет флопов или умножение матрицы на вектор для итерационных алгоритмов или оценку функций для интеграторов/оптимизаторов), хотя такие меры имеют свои недостатки.
Оценка
| ВИДЫ ДЕЯТЕЛЬНОСТИ | ПРОЦЕНТЫ |
|---|---|
| Наборы задач | 33% |
| Промежуточный экзамен | 33% |
| Последний проект | 34% |
Неделя 2 | Введение в численные методы | Математика
Лекция 3: Суммирование с плавающей запятой и обратная устойчивость
Резюме
Проанализированы накопленные ошибки округления с плавающей запятой (см. раздаточный материал ниже), объясняя результаты, которые мы наблюдали экспериментально в блокноте Джулии из предыдущей лекции. В этих экспериментах все входные данные были неотрицательными, так что фактор «числа обусловленности» в выводе равнялся 1. Однако в общем случае, если у вас есть сокращений между слагаемыми разных знаков, тот же анализ показывает, что относительная погрешность вывода может быть сколь угодно большой.
Стабильность: Дал очевидное определение точности, которую мы могли бы назвать «устойчивостью вперед» = почти правильный ответ для правильного ввода. Показал, что это часто слишком сильно; например добавление последовательности чисел не является устойчивым вперед. (В основном потому, что знаменатель в относительной прямой ошибке, который является точной суммой, может быть сделан сколь угодно малым с помощью отмен.)
Определим асимптотическое обозначение O(ε): f (ε) равно O( g (ε)), если существуют константы C, ε 0 > 0 такие, что | ф (ε)| <С| г (ε)| для всех |ε|<ε\(_0\). То есть g (ε) является асимптотическим верхней границей для f (ε) при стремлении ε к нулю без учета постоянных коэффициентов C. (Аналогичное обозначение используется в теории сложности вычислений, но в пределе большие аргументы n .) В определениях устойчивости мы технически требуем равномерной сходимости: мы должны иметь O(ε) ошибок с одними и теми же константами C и ε\(_0\), не зависящими от входных данных х . (Однако константы могут зависеть от размера x .)
В более общем случае мы применяем более слабое условие: «стабильность» = почти правильный ответ для почти правильного ввода.
Часто достаточно доказать «обратную устойчивость» = правильный ответ для почти правильного ввода. Показано, что в нашем примере сложения последовательности чисел обратная устойчивость работает там, где не работает прямая устойчивость. Затем более строго доказал, что суммирование с плавающей запятой n номеров обратно стабильны.
- Лекция 3, раздаточный материал 1: Заметки о точности наивного суммирования (PDF)
- Лекция 3, раздаточный материал 2: Обратная устойчивость рекурсивного суммирования (PDF)
Дополнительная литература
- Что должен знать каждый компьютерный ученый об арифметике с плавающей запятой, Дэвид Голдберг.
- Как операции с плавающей запятой в Java вредят всем и везде (PDF) Уильяма Кахана и Джозефа Дарси. Эта статья содержит хорошее обсуждение мифов и неправильных представлений о плавающей запятой.
- Прочитайте «Лекции 3 и 13–15» в учебнике Численная линейная алгебра .
- Статья в Википедии о нотации Big O; обратите внимание, что выражения типа O(ε) мы ищем в пределе малых аргументов, а не больших аргументов (как в теории сложности), но в остальном идеи те же.
Лекция 4: Нормы векторных пространств
Резюме
При квантификации ошибок центральным понятием является норма, и в нашем доказательстве обратной устойчивости суммирования мы видели, что выбор нормы кажется важным. Определенные нормы (как в лекции 3 Трефетена): для векторного пространства V , норма принимает любое v ∈ V и дает действительное число ‖ v ‖, удовлетворяющее трем свойствам:
- Положительно определенный: ‖ v ‖ ≥ 0 и = 0 тогда и только тогда, когда v = 0
- Масштабирование: ‖α v ‖ = |α|⋅‖ v ‖ для любого скаляра α.
- Неравенство треугольника: ‖ v + w ‖ ≤ ‖ v ‖ + ‖ w ‖
Существует множество норм для множества различных векторных пространств. Приведены примеры норм векторов-столбцов: нормы L\(_p\) (обычно \(p\) = 1, 2 или \(\infty\)) и взвешенные нормы L\(_2\). Полное (= непрерывное, по существу) нормированное векторное пространство называется банаховым пространством, и эти концепции ошибок обобщаются до f ( x ), когда f и x находятся в любых банаховых пространствах (включая скаляры, векторы-столбцы, матрицы, … хотя бесконечномерные банаховы пространства сложнее).
Особенно важны в численном анализе функции, в которых входы и/или выходы являются матрицами, и для этих случаев нам нужны матричные нормы. Наиболее важными матричными нормами являются те, которые связаны с матричными операциями. Начал с нормы Фробениуса. Связанные с нормой Фробениуса ‖ Умножение на унитарную матрицу Q ( Q * = Q -1 ) сохраняет как фробениусовские, так и L 2 индуцированные нормы.
Эквивалентность норм: Описан факт, что любые две нормы эквивалентны с точностью до постоянной границы, и показано, что это означает, что стабильность в одной норме подразумевает стабильность во всех нормах. Эскизное доказательство ( только бегло просмотрел это ): (i) показать, что мы можем свести проблему к доказательству того, что любая норма эквивалентна, например, L 1 на (ii) единичной окружности; (iii) показать, что любая норма непрерывна; и (ii) использовать результат реального анализа: непрерывная функция на замкнутом/ограниченном (компактном) множестве достигает своего максимума и минимума, теоремы об экстремальном значении. См. раздаточный материал ниже.
- Раздаточный материал к лекции 4: Заметки об эквивалентности норм (PDF)
Дополнительная литература
- Прочитать «Лекцию 3» в учебнике Числовая линейная алгебра .
- Если вы не сразу понимаете, что A*A имеет неотрицательные действительные собственные значения (это положительно полуопределенное), самое время вернуться к вашей линейной алгебре; см. также «Лекция 24» в учебнике Численная линейная алгебра .
Лекция 5: Номера состояний
Резюме
Связанная обратная ошибка с прямой ошибкой и обратная стабильность с прямой ошибкой (или «точность», как это называется в книге). Покажите, что в пределе высокой точности прямая ошибка может быть ограничена обратной ошибкой, умноженной на величину κ, относительное число обусловленности. Что хорошо в κ, так это то, что он включает только точную линейную алгебру и исчисление и полностью отделен от рассмотрения округления с плавающей запятой. Показал, что для дифференцируемых функций κ можно записать через индуцированную норму матрицы Якоби.
Расчетное число условия для извлечения квадратного корня, суммирования и умножения матрицы на вектор, а также решение Ax = b , аналогично книге. Определил число обусловленности матрицы: для f ( x ) = Ax число обусловленности равно ‖ A ‖⋅‖ x ‖/‖ Ax ‖/‖ Ax ‖‖ Ax ‖⋅‖ x ‖/‖ Ax ‖ ( А ) = ‖ А ‖⋅‖ А -1 ‖.
Связанная матрица L 2 норма собственных значений числа Б = А * А . B , очевидно, является эрмитовым ( B * = B ), и немного больше работы показало, что оно положительно полуопределенно: x * B x ≥ 0 для любых x . Рассмотрены и перевыведены свойства собственных значений и собственных векторов эрмитовых и положительно-полуопределенных матриц. Эрмитовость означает, что собственные значения действительны, собственные векторы ортогональны (или могут быть выбраны ортогональными). Кроме того, эрмитова матрица должна быть диагонализируемой (для этого я пропустил доказательство; мы докажем это позже в более общем случае). Положительно-полуопределенный означает, что собственные значения неотрицательны.
Доказано, что для эрмитовой матрицы B частное Рэлея R( x ) = x * Bx / x *x ограничено сверху и снизу наибольшим и наименьшим собственными значениями матрицы
9 B
(«теорема минимум–макс»). Следовательно, показано, что L 2 индуцированная норма A является квадратным корнем из наибольшего собственного значения B = A * A . Точно так же показал, что L 2 индуцирует норму A -1 , или, в более общем случае, верхняя грань ‖ x ‖/‖ Ax ‖, равна квадратному корню обратного наименьшего собственного значения A * A . Таким образом, Понимание норм и чисел обусловленности матриц сводится к пониманию собственных значений A * A (или AA *). Однако смотреть на это таким образом неудовлетворительно по нескольким причинам.