Вычислительные методы для инженеров
Вычислительные методы для инженеров
ОглавлениеПРЕДИСЛОВИЕГлава 1. МАТЕМАТИЧЕСКОЕ МОДЕЛИРОВАНИЕ И РЕШЕНИЕ ИНЖЕНЕРНЫХ ЗАДАЧ С ПРИМЕНЕНИЕМ ЭВМ § 1.2. Основные этапы решения инженерной задачи с применением ЭВМ § 1.3. Вычислительный эксперимент § 1.4. Дополнительные замечания Глава 2. ВВЕДЕНИЕ В ЭЛЕМЕНТАРНУЮ ТЕОРИЮ ПОГРЕШНОСТЕЙ § 2.1. Источники и классификация погрешностей результата численного решения задачи § 2.2. Приближенные числа. Абсолютная и относительная погрешности 2. Правила записи приближенных чисел. 3. Округление. § 2.4. Погрешность функции § 2.5. Особенности машинной арифметики 2. Представление целых чисел. 3. Представление вещественных чисел. 4. Арифметические операции над числами с плавающей точкой.  5. Удвоенная точность. 6. Вычисление машинного эпсилон. § 2.6. Дополнительные замечания Глава 3. ВЫЧИСЛИТЕЛЬНЫЕ ЗАДАЧИ, МЕТОДЫ И АЛГОРИТМЫ. ОСНОВНЫЕ ПОНЯТИЯ § 3.2. Обусловленность вычислительной задачи 2. Примеры плохо обусловленных задач. 3. Обусловленность задачи вычисления значения функции одной переменной. 5. Обусловленность задачи вычисления суммы ряда. § 3.3. Вычислительные методы § 3.4. Корректность вычислительных алгоритмов § 3.5. Чувствительность вычислительных алгоритмов к ошибкам округления § 3.6. Различные подходы к анализу ошибок § 3.7. Требования, предъявляемые к вычислительным алгоритмам § 3.8. Дополнительные замечания Глава 4. МЕТОДЫ ОТЫСКАНИЯ РЕШЕНИЙ НЕЛИНЕЙНЫХ УРАВНЕНИЙ § 4.2. Обусловленность задачи вычисления корня § 4.3. Метод бисекции § 4.4. Метод простой итерации § 4.5. Обусловленность метода простой итерации § 4.6. Метод Ньютона § 4.  § 4.8. Дополнительные замечания Глава 5. ПРЯМЫЕ МЕТОДЫ РЕШЕНИЯ СИСТЕМ ЛИНЕЙНЫХ АЛГЕБРАИЧЕСКИХ УРАВНЕНИЙ § 5.2. Нормы вектора и матрицы § 5.3. Типы используемых матриц § 5.4. Обусловленность задачи решения системы линейных алгебраических уравнений § 5.5 Метод Гаусса § 5.6. Метод Гаусса и решение систем уравнений с несколькими правыми частями, обращение матриц, вычисление определителей § 5.7. Метод Гаусса и разложение матрицы на множители. LU-разложение § 5.8. Метод Холецкого (метод квадратных корней) § 5.9. Метод прогонки § 5.11. Итерационное уточнение § 5.12. Дополнительные замечания Глава 6. ИТЕРАЦИОННЫЕ МЕТОДЫ РЕШЕНИЯ СИСТЕМ ЛИНЕЙНЫХ АЛГЕБРАИЧЕСКИХ УРАВНЕНИЙ § 6.1. Метод простой итерации § 6.2. Метод Зейделя § 6.3. Метод релаксации § 6.4. Дополнительные замечания Глава 7. МЕТОДЫ ОТЫСКАНИЯ РЕШЕНИЙ СИСТЕМ НЕЛИНЕЙНЫХ УРАВНЕНИЙ § 7.  2. Метод простой итерации§ 7.3. Метод Ньютона для решения систем нелинейных уравнений 7.4. Модификации метода Ньютона § 7.5. О некоторых подходах к решению задач локализации и отыскания решений систем нелинейных уравнений § 7.6. Дополнительные замечания § 8.2. Степенной метод § 8.3. Метод обратных итераций § 8.4. QR-алгоритм § 8.5. Дополнительные замечания Глава 9. МЕТОДЫ ОДНОМЕРНОЙ МИНИМИЗАЦИИ § 9.2. Обусловленность задачи минимизации § 9.3. Методы прямого поиска. Оптимальный пассивный поиск. Метод деления отрезка пополам. Методы Фибоначчи и золотого сечения § 9.4. Метод Ньютона и другие методы минимизация гладких функций § 9.5. Дополнительные замечания Глава 10. МЕТОДЫ МНОГОМЕРНОЙ МИНИМИЗАЦИИ § 10.1. Задача безусловной минимизации функции многих переменных § 10.2. Понятие о методах спуска. Покоординатный спуск § 10.3. Градиентный метод § 10.4. Метод Ньютона  5. Метод сопряженных градиентов§ 10.6. Метода минимизации без вычисления производных § 10.7. Дополнительные замечания Глава 11. ПРИБЛИЖЕНИЕ ФУНКЦИЙ И СМЕЖНЫЕ ВОПРОСЫ § 11.2. Интерполяция обобщенными многочленами § 11.3. Полиномиальная интерполяция. Многочлен Лагранжа § 11.4. Погрешность интерполяции § 11.5. Интерполяция с кратными узлами § 11.6. Минимизация оценки погрешности интерполяции. Многочлены Чебышева § 11.7. Конечные разности § 11.8. Разделенные разности § 11.9. Интерполяционный многочлен Ньютона. Схема Эйткена § 11.10. Обсуждение глобальной полиномиальной интерполяции. Понятие о кусочно-полиномиальной интерполяции § 11.12. Понятие о дискретном преобразовании Фурье и тригонометрической интерполяции § 11.13. Метод наименьших квадратов § 11.14. Равномерное приближение функций § 11.15. Дробно-рациональные аппроксимации и вычисление элементарных функций § 11.16. Дополнительные замечания Глава 12.  ЧИСЛЕННОЕ ДИФФЕРЕНЦИРОВАНИЕ§ 12.1. Простейшие формулы численного дифференцирования § 12.2. О выводе формул численного дифференцирования § 12.4. Дополнительные замечания Глава 13. ЧИСЛЕННОЕ ИНТЕГРИРОВАНИЕ 13.2. Квадратурные формулы интерполяционного типа § 13.3. Квадратурные формулы Гаусса § 13.4. Апостериорные оценки погрешности. Понятие об адаптивных процедурах численного интегрирования § 13.5. Вычисление интегралов в нерегулярных случаях § 13.6. Дополнительные замечания Глава 14. ЧИСЛЕННЫЕ МЕТОДЫ РЕШЕНИЯ ЗАДАЧИ КОШИ ДЛЯ ОБЫКНОВЕННЫХ ДИФФЕРЕНЦИАЛЬНЫХ УРАВНЕНИЙ § 14.1. Задача Коши для дифференциального уравнения первого порядка § 14.2. Численные методы решения задачи Коши. Основные понятия и определения § 14.3. Использование формулы Тейлора § 14.5. Модификации метода Эйлера второго порядка точности § 14.6. Методы Рунге-Кутты § 14.7. Линейные многошаговые методы.  Методы Адамса§ 14.8. Устойчивость численных методов решения задачи Коши § 14.9. Неявный метод Эйлера § 14.10. Решение задачи Коши для систем обыкновенных дифференциальных уравнений и дифференциальных уравнений m-го порядка § 14.11. Жесткие задачи § 14.12. Дополнительные замечания Глава 15. РЕШЕНИЕ ДВУХТОЧЕЧНЫХ КРАЕВЫХ ЗАДАЧ § 15.1. Краевые задачи для одномерного стационарного уравнения теплопроводности § 15.2. Метод конечных разностей: основные понятия § 15.4. Понятие о проекционных и проекционно-разностных методах. Методы Ритца и Гадеркина. Метод конечных элементов § 15.5. Метод пристрелки § 15.6. Дополнительные замечания |
Метод Гаусса. Большая российская энциклопедия
Научные методы исследования
Ме́тод Га́усса, метод решения системы линейных алгебраических уравнений; назван в честь К.
Гаусса.
Метод Гаусса состоит в приведении системы линейных алгебраических уравнений {a11x1+a12x2+…+a1nxn=b1a21x1+a22x2+…+a2nxn=b2……………am1x1+am2x2+…+amnxn=bm(1)\left\{\begin{alignedat}{3}
a_{11}x_1&+a_{12}x_2&+&\ldots&+ a_{1n}x_n&=b_1\\
a_{21}x_1&+a_{22}x_2&+&\ldots&+a_{2n}x_n&=b_2\\
&\mathellipsis\mathellipsis&&\mathellipsis&\mathellipsis\mathellipsis\\
a_{m1}x_1&+a_{m2}x_2&+&\ldots&+a_{mn}x_n&=b_m
\end{alignedat}\right.\tag1⎩⎨⎧a11x1a21x1am1x1+a12x2+a22x2……+am2x2+++…………+a1nxn+a2nxn……+amnxn=b1=b2=bm(1)к ступенчатому (треугольному) виду {p1j1xj1+p1j2xj2+…+p1jrxjr+…+p1jnxjn=β1p2j2xj2+…+p2jrxjr+…+p2jnxjn=β2………………………prjrxjr+…+prjnxjn=βr0=βr+1…0=βm(2)\left\{
\begin{alignedat}{10}p_{1j_1}x_{j_1}+p_{1j_2}x_{j_2}+&\ldots+&p_{1j_r}x_{j_r}+\ldots+p_{1j_n}x_{j_n}&=\beta_1\\
p_{2j_2}x_{j_2}+&\ldots+&p_{2j_r}x_{j_r}+\ldots+p_{2j_n}x_{j_n}&=\beta_2\\
&\ldots\ldots&\ldots\ldots\ldots\ldots\ldots\ldots&\ldots\\
& &p_{rj_r}x_{j_r}+\ldots+p_{rj_n}x_{j_n}&=\beta_r\\
&&0&=\beta_{r+1}\\
&&&\ldots\\
&&0&=\beta_m\\
\end{alignedat}\right.
Для преобразования системы используются элементарные преобразования, не меняющие множества решений: перестановка уравнений и прибавление к одному уравнению другого, умноженного на число. На первом шаге прямого хода выбирается неизвестная xj1x_{j_1}xj1, у которой хотя бы в одном уравнении системы (1) коэффициент отличен от нуля. Далее уравнения переставляются так, чтобы в первом уравнении a1j1≠0a_{1j_1}\neq0a1j1=0. Исключается неизвестная xj1x_{j_1}xj1 из остальных уравнений системы путём прибавления к kkk-му уравнению первого, умноженного на −akj1/a1j1-a_{kj_1}/a_{1j_1}−akj1/a1j1. На втором шаге оставляется без изменения первое уравнение и проделывается аналогичная процедура с остальными n−1n-1n−1 уравнениями.
Через конечное число шагов (не превышающее mmm) система принимает ступенчатый вид (2).
В отличие от метода Крамера и матричного метода, метод Гаусса применим к любым системам линейных алгебраических уравнений: число уравнений может быть не равно числу неизвестных, система может быть несовместна или не определена.
Если неоднородная система уравнений, приведённая к ступенчатому виду (2), содержит хотя бы одно уравнение вида 0=βk,βk≠0 0=\beta_k,\qquad\beta_k\neq00=βk,βk=0то система несовместна; если таких уравнений нет, система совместна.
На практике однородной системе линейных алгебраических уравнений сопоставляется матрица системы, а неоднородной системе – расширенная матрица системы. Преобразованиям системы соответствуют элементарные преобразования строк матрицы. Необходимое и достаточное условие совместности неоднородной системы определяется теоремой Кронекера – Капелли: система совместна тогда и только тогда, когда ранг матрицы системы (матрица, составленная из коэффициентов при неизвестных) равен рангу расширенной матрицы системы – матрицы, которая получается путём добавления к матрице системы справа столбца правых частей системы уравнений.
Если в совместной системе (2) число нетривиальных уравнений rrr равно числу неизвестных nnn, то матрица системы является треугольной и система имеет единственное решение. Если r<nr<nr<n, система имеет бесконечное множество решений. Переменные xj1,xj2,…,xjrx_{j_1},x_{j_2},\ldots,x_{j_r}xj1,xj2,…,xjr называются главными или зависимыми, остальные переменные – свободными или независимыми.
В ступенчатой системе (2) перенесём слагаемые со свободными переменными в правую часть уравнений. Получаем систему {p1j1xj1+p1j2xj2+…+p1jrxjr=β1−p1jr+1xjr+1−…−p1jnxjnp2j2xj2+…+p2jrxjr=β2−p2jr+1xjr+1−…−p2jnxjn…………………………………prjrxjr=βr−prjr+1xjr+1−…−prjnxjn.(3)\left\{\begin{alignedat}{10}p_{1j_1}x_{j_1}+p_{1j_2}x_{j_2}+&\ldots+&p_{1j_r}x_{j_r}&=\beta_1-p_{1j_{r+1}}x_{j_{r+1}}-\ldots-p_{1j_n}x_{j_n}\\
p_{2j_2}x_{j_2}+&\ldots+&p_{2j_r}x_{j_r}&=\beta_2-p_{2j_{r+1}}x_{j_{r+1}}-\ldots-p_{2j_n}x_{j_n}\\
&\ldots&\ldots\ldots&\ldots\ldots\ldots\ldots\ldots\ldots\ldots\ldots\ldots\ldots\\
&&p_{rj_r}x_{j_r}&=\beta_r-p_{rj_{r+1}}x_{j_{r+1}}-\ldots-p_{rj_n}x_{j_n}.
\end{alignedat}\right.\tag3⎩⎨⎧p1j1xj1+p1j2xj2+p2j2xj2+…+…+…p1jrxjrp2jrxjr……prjrxjr=β1−p1jr+1xjr+1−…−p1jnxjn=β2−p2jr+1xjr+1−…−p2jnxjn…………………………=βr−prjr+1xjr+1−…−prjnxjn.(3)В системе (3) матрица коэффициентов при главных переменных является треугольной. Главные переменные однозначно выражаются через свободные переменные, которые принимают любые значения.
Для минимизации вычислительной погрешности используется метод Гаусса с выбором главного элемента. На каждом шаге прямого хода перестановкой строк и столбцов преобразуемой матрицы добиваются того, чтобы главным элементом pkjkp_{kj_k}pkjk оказался максимальный по модулю элемент матрицы из всех с индексами больше либо равными kkk. При частичном выборе главного элемента в качестве главного элемента pkjkp_{kj_k}pkjk выбирается максимальный по модулю элемент kkk-й строки матрицы.
Имеются различные модификации метода Гаусса для решения задач с матрицами специального вида (симметричными, ленточными и т.
3}/{3}n3/3 операций.
Важной модификацией метода Гаусса является метод Гаусса – Жордана (метод полного исключения неизвестных), позволяющий получить систему (3) с единичной матрицей. Этот метод применяется также для нахождения обратной матрицы.
Осипов Юрий ВикторовичДата публикации: 3 февраля 2023 г. в 15:58 (GMT+3)
линейная алгебра – обратное исключение и обратная замена?
Задавать вопрос
спросил
Изменено 2 месяца назад
Просмотрено 1к раз
$\begingroup$
Я задал этот вопрос и получил ответ
Метод Гаусса превращает матрицу в верхнетреугольную, затем вы решаете треугольную систему
, но если «тогда вы решаете треугольную систему» означает, что вы решаете ее, используя операции с элементарными строками (также известные как элементарные операции со строками, которые выполняются для замены), эти два метода кажутся идентичными: чтобы как бы «заменить» переменные из уравнений), а в Гауссе вы используете замену, чтобы как бы заменить переменные из уравнений.
Поскольку ERO используются для замены этих переменных, они кажутся мне полностью идентичными. Может ли кто-нибудь помочь с этой путаницей? Они должны быть разными, но я не понимаю, как, если замена требует выполнения элементарных операций со строками в любом случае.
Я думал, что эта часть может быть вопросом сама по себе.
- линейная алгебра
$\endgroup$
$\begingroup$
Обратная подстановка — процедура решения системы линейных алгебраических уравнений $Ux=y$, где $U$ — верхняя треугольная матрица, диагональные элементы которой не равны нулю. Я думаю, что под обратным исключением подразумевается исключение Гаусса, процесс выполнения операций над строками для создания верхней треугольной матрицы.
Итак, если у вас есть система $Ax=b$, чтобы решить эту систему, вы можете выполнить исключение Гаусса (процесс применения операций со строками для получения верхней треугольной матрицы), чтобы получить $Ux=b’$.
Теперь, когда у вас есть верхняя треугольная матрица, вы можете выполнить обратную замену (то есть начать с $u_{n,n}x_{n}=b_n’$, а затем использовать это решение для решения уравнений для $x_{n-1 }$, затем $x_{n-2}$ и так далее).
Вкратце: Backs-sub — это решатель для системы с верхней треугольной матрицей, исключение Гаусса (возможно, также называемое обратным исключением) — это метод получения системы с верхней треугольной матрицей.
Дополнительные сведения см. в статьях Википедии по каждому из них: https://algowiki-project.org/en/Backward_substitution и https://en.wikipedia.org/wiki/Gaussian_elimination .
$\endgroup$
2
$\begingroup$
(немного запоздало, но, надеюсь, еще кому-нибудь пригодится)
В исключении Гаусса с обратной заменой мы сначала приводим систему уравнений к рядный эшелон из методом исключения.
опорных точек , ведущих коэффициентов, используются для создания нулей ниже . Затем мы используем замену для решения системы: начиная с самого нижнего уравнения, мы подставляем (заменяем) решения наших переменных в уравнения выше.
В исключении Гаусса-Джордана мы приводим систему к ряду сокращенного эшелона формы путем исключения. Повороты используются для создания нулей ниже и выше . После того, как в строке уменьшена форма эшелона, у нас есть решение.
Пожалуйста, смотрите https://en.wikipedia.org/wiki/Row_echelon_form для изображений этих эшелонированных форм.
Подводя итог, можно сказать, что в методе исключения Гаусса с обратной заменой мы исключаем нисходящие и заменяем восходящие; в исключении Гаусса-Жордана мы исключаем вверх и вниз.
$\endgroup$
Уилкинсон и обратный анализ ошибок
Опубликовано Ник Хайэм Оставить комментарий
Свен Хаммарлинг и Ник Хайам
Часто думают, что Джим Уилкинсон разработал метод обратного анализа ошибок из-за своего раннего участия в решении систем линейных уравнений. В своей лекции Тьюринга 1970 года [5] он описал опыт во время Второй мировой войны в Исследовательском отделе вооружений по решению системы двенадцати линейных уравнений на настольном компьютере с использованием исключения Гаусса. (Он не говорит, сколько времени это заняло, но определенно должно было пройти несколько дней.) Коэффициенты были порядка единицы, и, используя вычисление с десятичной запятой, он обнаружил, что коэффициенты определяющего сокращенного уравнения имеют четыре начальных нуля: поэтому он чувствовал, что в решениях наверняка может быть не более шести правильных цифр. В качестве проверки своих расчетов он затем вычислил остатки, и, к его удивлению, левые части совпали с правыми частями до полных десяти цифр.
Слайд Уилкинсона, описывающий решение системы 18 уравнений.
После войны Уилкинсон поступил на работу в отдел математики Национальной физической лаборатории. Вскоре после его приезда в отдел математики была передана система из восемнадцати уравнений. Это потребовало совместных усилий, которыми руководили Лесли Фокс, Эрик Гудвин, Алан Тьюринг и Уилкинсон. Опять же, решение было несколько плохо обусловлено, как показало окончательное сокращенное уравнение, но снова при вычислении невязок правая и левая части совпадали с полной точностью. Между прочим, Уилкинсон и его коллеги использовали итеративное уточнение, которое убедило их в том, что первое решение дало шестизначную точность.
Этот опыт не привел Уилкинсона напрямую к разработке обратного анализа ошибок. В [7] он говорит, что впервые применил обратный анализ ошибок в связи с простыми программами для вычисления нулей полиномов вскоре после того, как PILOT ACE стал использоваться, в частности, программу для вычисления полинома методом вложенного умножения и программу для выполнения полиномиальной дефляции.
Но он, тем не менее, не признавал обратный анализ ошибок в качестве общего инструмента. Уилкинсон объясняет
Естественно спросить, почему я сразу не приступил к использованию этого типа анализа ошибок в качестве инструмента общего назначения. Оглядываясь назад, кажется удивительным, что я не попробовал его на методе исключения Гаусса и на различных алгоритмах собственных значений, которыми я в то время очень интересовался. Правда в том, что мне ни на мгновение не пришло в голову сделать это.
Его явное признание инструмента, который он решил назвать обратным анализом ошибок , вскоре пришло благодаря его опыту решения задач на собственные значения на PILOT ACE. Далее в [7] он утверждает:
Из-за небольшого объема памяти PILOT ACE практически единственным алгоритмом, который можно было использовать для решения больших несимметричных задач на собственные значения, был степенной метод, дополненный различными методами ускорения сходимости.
После определения каждого собственного значения/собственного вектора эта пара удалялась дефляцией. В то время дефляция обычно считалась чрезвычайно неустойчивой, и поэтому я использовал ее сначала с большим трепетом. Однако вскоре стало очевидно, что это было удивительно эффективно.
После определения каждого собственного значения/собственного вектора эта пара удалялась дефляцией. В то время дефляция обычно считалась чрезвычайно неустойчивой, и поэтому я использовал ее сначала с большим трепетом. Однако вскоре стало очевидно, что это было удивительно эффективно.Как и в случае с линейным уравнением, Уилкинсон вычислил остатки, , где и – вычисленные значения, нормализовав их так, что , и даже после многих дефляций он обнаружил, что остатки были удивительно малы. Затем он понял, что
, и это привело его прямо к обратному анализу ошибок, поскольку, если мы положим , то и являются точным собственным значением и собственным вектором матрицы . Теперь он осознал, что этот процесс можно широко использовать, и это, конечно же, привело к его 1963 book Ошибки округления в алгебраических процессах [3] и, вскоре после этого, до Алгебраическая проблема собственных значений [4].
Следует отметить, что Уилкинсон не претендовал на роль первого, кто выполнил обратный анализ ошибок.
Он приписывает первый анализ фон Нейману и Голдстайну в их статье 1947 года [2], которая, как сказал Уилкинсон в своей премии фон Неймана, «не то чтобы чтение перед сном» [6]. Уилкинсон также отдает должное Гивенсу за его обратный анализ ошибок ортогональной трехдиагонализации в его, к сожалению, неопубликованном техническом отчете [1].
Ссылки
[1] В. Гивенс. Численный расчет характеристических значений вещественной симметричной матрицы. Технический отчет ORNL-1574, Окриджская национальная лаборатория, Ок-Ридж, Теннесси, 37831, США, 1954 г.
[2] Дж. фон Нейман и Х. Х. Голдстайн. Численное обращение матриц высокого порядка. Бык. амер. Мат. соц. , 53:1021–1099, 1947.
[3] Дж. Х. Уилкинсон. Ошибки округления в алгебраических процессах. Заметки по прикладным наукам, №32. HMSO, Лондон, Великобритания, 1963. (Также опубликовано Prentice-Hall, Englewood Cliffs, NJ, USA, 1964. Перепечатано Dover Publications, New York, 1994).
[4] Дж.