что такое сходимость метода
Понятия точности, устойчивости и сходимости
При численном решении
При выборе численного метода необходимо оценить такие его характеристики, такие как точность, устойчивость и сходимость.
Точность – это мера близости численного решения к точному, или истинному, решению.
Устойчивость. При решении инженерных задач неизбежно появляются погрешности исходных данных (входных параметров). Поэтому возникает вопрос о том, насколько чувствительными могут оказаться сами задачи и их решения к таким погрешностям.
Если решение существует и единственно, то возможны два варианта.
1. Решение задачи непрерывно зависит от входных параметров, т.е. малым изменениям входных параметров (возмущениям) соответствует малое изменение решения задачи. Такое решение называется устойчивым, а сама задача – корректной.
2. Если же небольшие возмущения исходных данных приводят к большим изменениям решения, то это решение называется неустойчивым, а сама задача – некорректной.
Корректность. Задача называется поставленной корректной, если решение существует, единственно и устойчиво относительно исходных данных из некоторого класса ее решений. [8, 12].
Применять ЧМ для решения некорректно поставленных задач нецелесообразно, поскольку погрешности округления, возникающие в расчетах, будут быстро возрастать по ходу вычислений, что приведет к существенным искажениям результатов.
Сходимость – это постепенное приближение последовательно вычисляемых приближенных решений к предельному (точному) решению.
Термин сходимости применяется к построению итерационной последовательности, в которой одно приближенное решение (итерация) становится исходной информацией для следующего приближенного решения.
Таким образом, в сходящемся процессе разница между соседними приближениями (итерациями) уменьшается, стремясь в пределе к нулю.
Итак, чтобы получить решение задачи с необходимой точностью, ее постановка должна быть корректной, а применяемый ЧМ должен обладать устойчивостью и сходимостью.
Глава 1
Основные понятия матричного исчисления
Матричная форма расчетов известна давно. Однако до появления ЭВМ она не находила широкого применения из-за трудоемкости матричных операций при ручном счете.
Решение алгебраических задач при расчете строительных объектов требует знания матричного аппарата,так как, работая на ЭВМ, удобнее всего процесс расчета представлять в матричном виде. Чтобы далее при решении задач не обращаться к специальным руководствам, напомним основные понятия, которые в дальнейшем потребуются нам при изучении данного курса.
Матрицы и векторы.
Матрица – прямоугольная таблица, составленная из элементов (чисел), и имеющая mстрок и nстолбцов (размерность m ´ n), Обозначается матрица чаще всего большими буквами A или [A]:
Если m = n, матрица называется квадратной
Еслиm =1, этоматрица-строка (вектор-строка);
Две матрицы и
равныдруг другу, если они одного типа (имеют одинаковое число строк и столбцов – размер [m´n]) и соответствующие элементы этих матриц равны между собой:
для всех i и j.
Если n = 1, то матрица называется матрица-столбец или вектор. Будем особо выделять вектор и обозначать его следующим образом :
Квадратная матрица, у которой все элементы равны нулю, кроме элементов стоящих на главной диагонали, называется диагональной:
A
Диагональная матрица, у которой элементы, стоящие на главной диагонали равны 1, называется единичнойи обозначается обычно буквой Е:
E
Если в матрице строки и столбцы поменять местами, получается транспонированнаяматрица (обозначается А т ).
Алгоритм преобразования матрицы к треугольному виду приведен во второй главе.
Эквивалентны следующие высказывания: матрица А является невырожденной, если:
· столбцы (строки) матрицыА линейно независимы;
· равенство , означает, что
;
Обратная матрица.Доказывается теорема, что если матрица А невырожденная (det A ≠ 0), то она имеет обратную матрицу (обозначается А -1 ).
Матрица называется обратнойпо отношению к данной, если ее умножение как справа, так и слева на данную матрицу дает единичную матрицу:
Процесс нахождения обратной матрицы называется обращением матрицы.
Матрицы специального вида
При использовании численных методов для решения задач строительства приходится сталкиваться с матрицами, специальная форма которых позволяет облегчить процесс вычисления. Рассмотрим некоторые из них.
Матрица, в которой большинство элементов равно нулю, называется разреженной. Такие матрицы появляются при расчетах моделей, в которых существенно локализованы связи и действующие нагрузки (стержневые системы, например, фермы), или при разностной аппроксимации дифференциальных уравнений. Элементы aij такой матрицы обычно вычисляются по заданным формулам и их можно не хранить в оперативной памяти машины. Это очень важно, так как порядок таких матриц может достигать нескольких десятков и даже сотен тысяч.
Ленточная матрица – это разреженная матрица, в которой все ненулевые элементы расположены симметрично относительно главной диагонали.
Такие матрицы встречаются при решении краевых задач методом конечных разностей или вариационными методами – Ритца, конечных элементов.
Структуру ленточной матрицы можно представить в виде:
A
Трехдиагональная матрица – частный случай ленточной матрицы, ширина ленты которой равна 3 (или
каждая строка матрицы содержит три ненулевых элемента, за исключением первой и последней, содержащих по два ненулевых элемента).
Такого вида матрицы получаются при решении краевых задач, описываемых обыкновенными дифференциальными уравнениями, или при определении критических сил способом упругих грузов.
Квадратная матрица называется симметричной, если ее элементы симметричны относительно главной диагонали, ( ). Многие физические задачи равновесия, строительной механики приводят к симметричным матрицам.
Решение систем линейных алгебраических уравнений не представляет никаких затруднений для диагональных матриц, в которых элементы при всех i и j, кроме i= j.
Такого вида матрицы получаются при решении систем линейных алгебраических уравнений методом Жордана – Гаусса. Правда, привести матрицу к диагональному виду не просто.
Треугольные матрицы встречаются при решении систем линейных алгебраических уравнений (СЛАУ)методом Гаусса. И интересны тем, что решение СЛАУ сводится к рекуррентным (последовательным) вычислениям неизвестных.
Введение
Численные методы представляют собой отдельную область математики и применяются в различных прикладных направлениях. В частности, с помощью численных методов решаются и проблемы прикладной оптики. В данном пособии приводится обзор основных численных методов, чаще всего используемых при решении задач прикладной оптики. Особенностью пособия является использование в качестве заданий не просто математических функций, а реальных задач из области прикладной оптики, на примере которых рассматриваются численные методы. Это дает не только хорошее понимание сути самих численных методов, но и особенности их применения на практике.
Процесс решения любой сложной задачи, моделирования какого-то оптического процесса, можно представить как последовательность этапов.
Физическая постановка задачи. На этом этапе необходимо грамотно сформулировать и поставить задачу с точки зрения физики процесса. Для этого необходимо изучить рассматриваемую проблему и обладать знаниями в соответствующей области.
Математическая постановка задачи. На этом этапе нужно переформулировать физическую проблему на математический язык, то есть описывать в виде интегралов, систем уравнений, и т.д. Математическая модель должна корректно описывать основные законы физического процесса. В некоторых случаях на этом этапе можно остановиться, так как если задача простая, то существуют стандартные методы, которые нужно применить для решения этой задачи.
Метод непрерывной математики. На этом этапе оперируют не конечными числами, а функциями, общими величинами, то есть ищут решение проблемы в общем виде, и описывают при помощи математических формул.
Численные методы. Решение проблемы представляют в виде конечных математических операций – сложение, умножение. Численные методы позволяют свести решение задачи к выполнению конечного количества арифметических действий над числами, при этом результаты получаются в виде числовых значений. Чаще всего возможно использование известных стандартных численных методов.
Алгоритмизация. Алгоритмизация служит для упорядочения производимых действий в виде точного формального описания процесса. Алгоритм можно изобразить в виде блок-схемы или описать другим способом.
Программирование. На этом этапе алгоритм реализуется на каком-нибудь языке программирования высокого уровня.
Отладка программы. На этом этапе выполняется поиск ошибок, которые могли появиться на предыдущих этапах. Программа испытывается на решении тестовых задач для получения уверенности в достоверности результатов. Вполне вероятно, что придется вернуться в самое начало, к изменению физической постановки задачи, или какому-то другому этапу.
Проведение расчетов. На этом этапе готовятся исходные данные для расчетов, и проводятся вычисления по отлаженной программе.
Анализ результатов. Результаты расчетов анализируются, оформляется научно-техническая документация.
Все численные методы обладают некоторым набором характеристик. Наиболее важной из них является точность. На всех этапах решения задачи могут возникать погрешности, искажающие результаты вычислений, которые и определяют точность. Причины возникновения вычислительных погрешностей и способы их устранения рассматриваются в Приложении А.
При анализе точности одним из важнейших критериев является сходимость численного метода. Для дискретных методов (методы, которые заключаются в замене задачи с непрерывными функциями на задачу, в которой значения функций заданы в фиксированных точках) сходимость – это стремление значений решения метода к соответствующим значениям решения исходной задачи при стремлении к нулю параметра дискретизации (например, шага интегрирования).
Задача называется поставленной корректно, если для любых значений исходных данных из некоторого класса ее решение существует, единственно и устойчиво. Применять для решения некорректно поставленных задач численные методы, не имеет смысла, поскольку возникающие в расчетах погрешности округления будут сильно возрастать в ходе вычислений, что приведет к значительному искажению результатов.
Устойчивость – это чувствительность метода к неточностям в исходных данных. Задача называется устойчивой, если малые погрешности в исходной величине приводят к малым погрешностям в решении. Отсутствие устойчивости означает, что даже незначительные погрешности в исходных данных приводят к большим погрешностям в решении или даже к неверному результату. О неустойчивых задачах также говорят, что они чувствительны к погрешностям исходных данных.
Таким образом, для получения решения задачи с необходимой точностью ее постановка должна быть корректной, а используемый численный метод должен обладать устойчивостью (корректностью) и сходимостью.
В большинстве случаев, кроме точности (сходимости, устойчивости, корректности) необходимо следить за минимизацией трудоемкости решения. Применительно к вычислительным задачам трудоемкость определяется объёмом памяти, используемым в процессе поиска решения, и временем, необходимым для выполнения вычислений. Время обычно измеряется в количестве элементарных операций (сложения, умножения, и т.д.), которые необходимо выполнить для решения задачи. Эти характеристики желательно уменьшать построением оптимальных алгоритмов вычисления, не потеряв при этом в точности. К сожалению, часто уменьшение трудоемкости и увеличение точности являются взаимоисключающими параметрами, и главной задачей является найти баланс между ними.
Понятие сходимости
При анализе точности вычислительного процесса одним из важнейших критериев является сходимость численного метода. Она означает близость получаемого численного решения задачи к истинному решению. Строгие определения разных оценок близости могут быть даны лишь с привлечением аппарата функционального анализа. Здесь мы ограничимся некоторыми понятиями сходимости, необходимыми для понимания последующего материала.
Рассмотрим понятие сходимости итерационного процесса. Этот процесс состоит в том, что для решения некоторой задачи и нахождения искомого значения определяемого параметра (например, корня нелинейного уравнения) строится метод последовательных приближений. В результате многократного повторения этого процесса (или итераций) получаем последовательность значений x1, x2,. , xn. Говорят, что эта последовательность сходится к точному решению х = а, если при неограниченном возрастании числа итераций предел этой последовательности существует и равен а: . В этом случае имеем сходящийся численный метод.
Другой подход к понятию сходимости используется в методах дискретизации. Эти методы заключаются в замене задачи с непрерывными параметрами на задачу, в которой значения функций вычисляются в фиксированных точках. Это относится, в частности, к численному интегрированию, решению дифференциальных уравнений и т.п. Здесь под сходимостью методапонимается стремление значений решения дискретной модели задачи к соответствующим значениям решения исходной задачи при стремлении к нулю параметра дискретизации (например, шага интегрирования).
При рассмотрении сходимости важными понятиями являются ее вид, порядок и другие характеристики. С общей точки зрения эти понятия рассматривать здесь нецелесообразно; к ним будем обращаться при изучении конкретных численных методов.
Таким образом, для получения решения задачи с необходимой точностью ее постановка должна быть корректной, а используемый численный метод должен обладать устойчивостью (корректностью) и сходимостью.
Погрешности и их оценка. Сходимость численных методов
В целом погрешности разделяют на:
а) погрешности выбора расчетной схемы, которые обсуждаются в строительной механике, и, выбрав расчетную схему, влиять на эти погрешности мы больше уже не можем (это, собственно, неустранимые погрешности).
б) погрешности построения математической модели (метода расчета), определяемые тем, насколько точно мы определили зависимости, описывающие рассматриваемую задачу и метод ее решения, – эти погрешности также
являются неустранимыми, так как они неизбежны в рамках данной математической модели;
следует заметить, что все методы расчета сооружений (статический, кинематический методы, метод сил, метод перемещений и т.д.), которые мы условно называем точными, основываются на определенных допущениях, и эти допущения являются источником погрешностей в сравнении с действительной работой сооружений.
в) при переходе от математической модели к численному методу возникают погрешности численного метода; чаще всего это погрешности дискретизации, связанные с заменой математической модели решения задачи системой конечного количества линейных алгебраических уравнений или конечного
числа слагаемых – при разложении в ряд, и тому подобное. Этим типом
погрешности можно управлять, регулировать его величину (как мы видим
на примере вычисления ); она может быть уменьшена до заданного разумного значения путем изменения определенных параметров – например, шага численного интегрирования, числа членов ряда и т.п. Погрешность метода обычно стараются довести до величины, меньшей погрешности исходных данных (если она известна), так как дальнейшее снижение погрешности бессмысленно, и приводит только к увеличению объема вычислений, или до некоторой задаваемой величины.
г) при проведении расчетов вручную, на калькуляторе или на компьютере возникают погрешности округления, учитывая, что представление чисел и
на калькуляторе, и в компьютере происходят не точно, а с округлением;
максимальная погрешность при округлении может быть вычислена по формуле [3], где
– основание системы счисления,
– количество разрядов мантиссы числа, заложенных в устройство.
Таким образом, погрешности разделяются по причине возникновения
(погрешности расчетных схем, метода расчета, численного метода, погрешности округления) и могут быть неустранимыми или такими, которые можно, пусть частично, регулировать (уменьшать).
Погрешности могут быть абсолютными и относительными.
Если а – истинное значение, а – приближенное значение, то:
– абсолютная погрешность;
– относительная погрешность.
Относительную погрешность часто удобно вычислять в процентах:
;
.
Введем еще одно понятие – сходимость численного метода, которое обозначает приближение (стремление) результата численного метода к истинному решению.
Различают сходимость итерационного процесса, когда при решении задачи для нахождения искомых значений многократно повторяют какой-то процесс (выполняют последовательные итерации), получая последовательность решений (значений). Говорят, что эта последовательность сходится к точному решению, если при неограниченном возрастании числа итераций решение все ближе приближается к действительному и в пределе (при устремлении числа итераций к бесконечности) равно ему. К таким задачам относятся, например, задача нахождения корня нелинейного уравнения, задача решения системы линейных и нелинейных систем уравнений итерационными методами.
К таким задачам относится и задача вычисления
при разложении его
в ряд. Чем больше членов ряда мы возьмем, тем ближе его значение будет приближаться к действительному; при этом значения последних слагаемых здесь должны все более уменьшаться. Скорость этого уменьшения характеризует
скорость процесса схождения итерационного процесса (см. представленный ниже рисунок).
Естественно, чем быстрее сходится процесс, тем лучше, потому что в этом случае для получения приемлемого результата с заданной погрешностью
можно будет взять меньше членов ряда, или выполнить меньше итераций
(повторений процесса), что уменьшает объем вычислений.
Другой подход к понятию сходимости используется в методах дискретизации, в которых задача с непрерывными параметрами заменяется задачей, в
которой значения функции вычисляются в фиксированных точках. Такой подход используется, например, в численном интегрировании, в методе конечных разностей, в методе конечных элементов и т.п. Здесь под сходимостью метода понимается стремление значений решения дискретной модели к соответствующим значениям решения исходной задачи при стремлении к нулю параметра дискретизации (например, шага интегрирования, размеров конечных элементов в МКЭ и т.д.).
Большая Энциклопедия Нефти и Газа
Сходимость численных методов широко освещена в литературе. Однако все эти материалы мало пригодны для случаев решения нелинейных уравнений. [1]
Сходимость численного метода тесно связана с его корректностью. Тогда дискретная модель этой задачи должна быть построена таким образом, чтобы свойство корректности сохранилось. Таким образом, в понятие корректности численного метода включаются свойства однозначной разрешимости соответствующей системы уравнений и ее устойчивости по входным данным. Под устойчивостью понимается непрерывная зависимость решения от входных данных, равномерная относительно числа уравнений, составляющих дискретную модель. [2]
Сходимость численных методов широко освещена в литературе. Однако все эти материалы мало пригодны для случаев решения нелинейных уравнений. [3]
Для исследования сходимости численного метода по количеству координатных функций и шагу ведущего параметра, а также для проверки эффективности предлагаемого подхода решен ряд задач упругого деформирования и устойчивости круглых пластин, сферических и конических оболочек. Результаты решений предшествуют анализу соответствующих задач ползучести. Некоторые из них сравниваются с данными литературы. Кроме того, целью предварительных расчетов является также оценка критических нагрузок, знание которых интересно при изучении устойчивости оболочек в условиях ползучести. [4]
Конечно, здесь иначе, чем в случае обыкновенных дифференциальных уравнений, обстоит дело с обоснованием сходимости численных методов и оценкой погрешности. Для широких классов типовых задач такие исследования проведены. Однако для многих важных классов прикладных задач, предъявляемых математикам для решения, не только не доказан, но часто остается неясным сам факт существования решения. [10]
Теория разностных схем в основном развита для линейных задач и опирается, как отмечалось ранее, на три основных понятия: аппроксимацию исходных Дифференциальных уравнений, устойчивость вычислительного процесса, сходимость численного метода к решению. Для нелинейных задач теория, как правило, не развита; исследование устойчивости в этих случаях сопряжено с большими трудностями и проводится обычно на линейных аналогах конкретной задачи. Например, при исследовании устойчивости задач газовой динамики часто рассматриваются уравнения в акустическом приближении. [12]
Сходимость численного метода при решении стационарных задач методом итераций может существенным образом зависеть от выбранного начального приближения Ф для искомой функции. [13]