Численные методы (вычислительные методы, методы вычислений)

Лекция №1. Введение Численные методы (вычислительные методы, методы вычислений) — раздел вычислительной математики, изучающий приближенные способы решения типовых математических задач, которые либо не решаются, либо трудно решаются точными, аналитическими методами (вычислительная математика в узком смысле). Примерами типовых задач являются численное решение уравнений, численные дифференцирование и интегрирование и др. Кроме численных методов, к вычислительной математике относят круг вопросов, связанных с использованием компьютеров и программированием. Деление методов вычислений на аналитические и численные несколько условно. Например, при аналитическом решении квадратного уравнения 𝑎𝑥 2 + 𝑏𝑥 + −𝑏±√𝑏2 −4𝑎𝑐 𝑐 = 0 по известной формуле 𝑥1,2 = в ответ входит корень. Если он не 2𝑎 извлекается точно, то для получения численного значения корней потребуется численная процедура приближенного вычисления корня. В XXI в. численные методы интенсивно применяются для моделирования и проектирования различных систем, создается и используется большое количество математических программных пакетов. Но, несмотря на это, вопрос оценки их точности и достоверности стоит очень остро. Как известно, существует много задач, получить решение которых в аналитическом виде не удается, например, 2 решить уравнение 𝑥 + e𝑥 = 0, найти первообразную от e𝑥 , и т.п. Но для моделирования реальных, интересных с точки зрения практики процессов нужно уметь решать задачи существенно более сложные. Какими средствами мы обладаем кроме аналитического аппарата математики? Как известно, сейчас имеются компьютеры, которые по своим возможностям (миллионы и более операций в секунду) во много раз превосходят вычислительные способности человека. Но надо учесть, что эти операции суть не что иное, как четыре арифметических действия и простейшие логические функции. Т.е. компьютер – это очень мощный арифмометр. Но если речь идет о вычислении интегралов и трансцендентных функций, то решение этих задач не сводится к конечному числу арифметических операций. Таким образом, необходимо научиться решать задачи, которые решить нельзя, причем на оборудовании, которое принципиально для этого непригодно – парадоксальная проблема! Чтобы разобраться, в чем причина возникшего парадокса, необходим небольшой экскурс в историю. В свое время «изобретение» иррационального числа имело глобальное значение для дальнейшего развития математики. Понятия предела, производной и интеграла остаются основой современной математики. Невозможно представить нашу цивилизацию без авиации, космонавтики, высоких технологий, развитие которых не могло бы иметь места без математического моделирования, базирующегося на дифференциальном и интегральном исчислении. Эти виртуальные объекты и понятия стали настолько естественными, «реальными» не только для «чистого» математика, но и для любого исследователя, имеющего дело с математическими моделями, что идеальность, противоестественность этих объектов и понятий виртуальной реальности часто забывается. Ограниченность ресурсов (по времени, по памяти, по разрядности и по надежности), с которой приходится сталкиваться любому, кто применяет для исследований реальные приборы и технику, входит в противоречие с этой идеальностью. На самом деле, число π можно только вообразить, поскольку для записи его бесконечного количества цифр нужно бесконечное время, бесконечная память, бесконечная разрядность сопроцессора (чтобы иметь возможность производить арифметические операции) и идеальная надежность (чтобы не ошибиться в записи цифр). Итак, в реальности не существует ни иррациональных чисел, ни пределов, ни производных, ни интегралов. Но необходимо заметить, что не существует только абсолютно точных, идеальных величин. Приближенно можно представить и практически получить буквально все. В этом и состоит разрешение парадокса: в отказе от идеальности. При этом приобретаются огромные возможности: использование компьютера, решение очень сложных задач, причем даже в реальном масштабе времени (моделирование процессов во время их исполнения). Каковы же потери? Неточность, приближенность получаемых результатов не противоречит практическим потребностям, поскольку все используемые в реальных вычислениях числа имеют свои допуски, пределы возможной неточности. Поэтому точное знание используемых чисел для практических целей и не нужно. Потерей является всеобщность, универсальность аналитических решений, когда для получения частного решения можно лишь подставить необходимые исходные данные в полученную формулу. Численные решения всегда частные, и сколько бы их ни было, нерешенных вариантов остается бесконечно много. И это обстоятельство порождает дополнительную задачу перехода от частного к общему. Расплатой за приобретенные возможности также является появление новой реальности – погрешности, которой не было при точном решении задачи. Итак, даже в тех случаях, когда можно далеко продвинуться в аналитическом решении задачи, не исключено применение на каком-либо этапе численных методов для получения ответа в практически удобном виде. Часто аналитические методы называют «точными», а численные — «приближенными». Приведенные примеры показывают, что и аналитические методы могут приводить к приближенному результату. Кроме того, аналитические методы решения прикладных задач (в частности, в теоретической механике и физике) часто являются приближенными по существу, оставаясь аналитическими — например, когда функция заменяется первыми слагаемыми ее ряда Тейлора (степенной ряд): отбрасывание последующих слагаемых ряда вносит искажения в получаемый результат, даже если дальнейшие вычисления – аналитические. Заметим, что при прочих равных условиях аналитическое решение задачи на ЭВМ (в соответствующем пакете аналитических (символьных) вычислений — Maple, Mathematica, MATLAB, Mathcad и пр.) выполняется гораздо медленнее, чем численное. Тема 1. ПОГРЕШНОСТИ 1.1. Классификация погрешностей Поскольку вычислительные методы предназначены для отыскания приближенного решения задач, не решаемых точными методами, такому решению всегда свойственна некоторая погрешность. Рассмотрим источники погрешности. Погрешность модели. Природа слишком сложна и многообразна, чтобы пытаться изучать ее во всей полноте присущих ей, в том числе и малозначимых, взаимосвязей. Любая (естественная) наука изучает не природу непосредственно, а те модели, которые создаются самой этой наукой для описания природных явлений. Модель — это идеализированное описание явления, в котором выявлены основные и игнорируются второстепенные свойства явления. Хорошая модель — это верный шарж, меткая «карикатура» на изучаемое явление. Естественно, что моделирование, сопровождаемое огрублением и упрощением, вносит погрешность в результат описания явления. Математическая модель создается на языке математики, но оценка погрешности математической модели есть прерогатива не математики, а той науки, в рамках которой изучается явление. Погрешность исходных данных. Как правило, математическая модель содержит некоторые параметры, зависящие от исходных данных. Так как исходные данные обычно определяются из экспериментов, неизбежно сопровождаемых ошибками измерений, возникает погрешность исходных данных. Возникает вопрос: не может ли погрешность исходных данных (пусть даже малая) непоправимо «испортить» получаемый результат? Иногда это действительно возможно — такие задачи называются некорректными (и это как раз многие задачи, представляющие практический интерес). Современная вычислительная математика выработала способы их регуляризации, т.е. замены некорректной задачи близкой к ней в некотором смысле корректной задачей, в которой малое изменение исходных данных приводит к малому изменению результата. Погрешности в решении, обусловленные моделированием и исходными данными, называются неустранимыми. Они не зависят от математики и присутствуют даже в том случае, если решение поставленной математической задачи найдено точно. Погрешность метода. После того, как математическая модель создана, вычисления в рамках модели обычно можно выполнять по-разному. Сложная математическая задача заменяется более простой. Например, вычисление определенного интеграла заменяется вычислением интегральной суммы. При этом неизбежно возникает погрешность метода вычислений, которой в дальнейшем мы будем уделять большое внимание при рассмотрении конкретных численных методов. Погрешность округления. Любые расчеты, выполняемые как вручную, так и с помощью вычислительной техники, производятся с конечным числом цифр, поэтому приходится прибегать к округлению промежуточных результатов и окончательного ответа. Так возникает погрешность округления, которая может накапливаться в ходе вычислений (опасный процесс, способный обесценить результат вычислений!). Даже те результаты, которые получены точными аналитическими методами, испытывают влияние погрешности округлений и в действительности могут оказаться приближенными. Полная погрешность является результатом взаимодействия разных видов погрешностей и не может быть меньше, чем наибольшая из составляющих ее погрешностей. 1.2. Абсолютная и относительная погрешности Для оценки погрешности вводятся понятия абсолютной и относительной погрешности. Пусть х — точное значение некоторой величины (нам оно неизвестно и никогда не будет известно, поскольку определяется оно с помощью измерений, страдающих неточностями); а — приближенное значение той же величины (𝑎 ≈ 𝑥). Абсолютная погрешность приближенного числа а определяется как ∆𝑎 = |𝑥 − 𝑎|. Но поскольку х неизвестно, то и абсолютную погрешность мы узнать не можем. Чтобы разрешить парадокс, вводят предельную абсолютную погрешность: ∆∗𝑎 − такое значение, которое абсолютная погрешность заведомо не превзойдет при данном способе измерений: |𝑥 − 𝑎| ≤ ∆∗𝑎 . (1) ∗ Из формулы (1) следует, что 𝑎 − ∆𝑎 ≤ 𝑥 ≤ 𝑎 + ∆∗𝑎 , поэтому желательно возможно меньшее значение ∆∗𝑎 − это уменьшит длину интервала, содержащего искомое значение х, и тем самым понизит неопределенность в наших знаниях об этой величине. В технике формулу (1) часто записывают в виде 𝑥 = 𝑎 ± ∆∗𝑎 , причем ∆∗𝑎 называется допусками. Никакое изделие не может быть изготовлено с абсолютно точным соблюдением номинальных размеров; допуски показывают возможные (допустимые) отклонения от номинала. Итак, абсолютная погрешность оценивает точность измерений, но эта оценка неполна, поскольку не учитывает характерный размер изучаемого явления (объекта). Например, абсолютная погрешность в 1 см при измерении длины комнаты — вполне приемлемая точность, но при измерении высоты стола эта же погрешность будет сочтена достаточно грубой. Более информативным показателем качества измерений является относительная погрешность 𝜹𝒂 (соответственно предельная относительная погрешность 𝛿𝑎∗ ) приближенного числа а , определяемая как отношение абсолютной погрешности (предельной абсолютной погрешности) к модулю числа а: 𝛿𝑎 = ∆𝑎 (𝛿𝑎∗ = ∆∗𝑎 ) 𝑎 Относительная погрешность является величиной безразмерной, т.е. не зависит от выбора системы единиц измерения, что позволяет сравнивать качество измерений разнородных величин (бессмысленным является вопрос о том, что больше: 1 кг или 1 м, но сравнение качества измерений массы и длины в терминах относительной погрешности вполне допустимо). Измеряется 𝛿𝑎 (𝛿𝑎∗ ) в долях единицы или процентах. Пример. Согласно ныне действующим (2016 г.) определениям международного Комитета по константам для науки и технологии входящая в закон всемирного тяготения гравитационная постоянная равна γ= (6,67259 ± 0,00085) ·10−11 м3 ∙ кг−1 ∙ с−2 , а заряд электрона e = (1,60217733 ± 0,00000049) ·10−19 Кл. Какая величина определена точнее? Вычислим предельную относительную погрешность для гравитационной постоянной 𝛿𝛾∗ и для заряда электрона 𝛿𝑒∗ : 0,00085 𝛿𝛾∗ = = 1,27 ∙ 10−4 6,67259 0,00000049 𝛿𝑒∗ = = 3,1 ∙ 10−7 1,60217733 Таким образом, в последнем случае относительная погрешность оказывается на три порядка меньшей, т.е. заряд электрона определен существенно точнее, чем гравитационная постоянная. С понятиями абсолютной и относительной погрешности связаны понятия верных и значащих цифр. Цифры, составляющие приближенное число, могут быть значащими, верными и сомнительными. Значащими цифрами числа называются все цифры в его записи, начиная с первой ненулевой слева. Например, число 120∙103 имеет 3 значащие цифры; 0,514·10 имеет 3 значащие цифры; Числа 0,001307 и 6,0400 имеют соответственно четыре и пять значащих цифр. Итак, нули, находящиеся слева, значащими не являются, а нуль, записанный в конце десятичной дроби, всегда является значащей цифрой. Цифра называется верной, если граница абсолютной погрешности данного приближенного значения числа не больше единицы того разряда, в котором записана эта цифра. В противном случае цифра называется сомнительной. Пусть х= 398,65 ± 0,03. Имеем: 0,03 – граница абсолютной погрешности Единица последнего разряда – 0,01 (сотые доли) 0,03 > 0,01, значит, цифра 5 – сомнительная. 𝑎 Далее: 0,03 < 0,1 – значит, цифра 6 – верная. Если в записи приближенного значения числа какая-то цифра верная, то все предшествующие ей цифры тоже верные. Первую отброшенную (неверную) цифру часто называется сомнительной. Тема 2. ПРИБЛИЖЕНИЕ ФУНКЦИЙ Приближением (аппроксимацией) функции 𝑓(𝑥) называется отыскание функции 𝑔(𝑥), близкой в некотором смысле к 𝑓(𝑥). Аппроксимирующая функция 𝑔(𝑥) должна быть «проще» исходной. Как понимается близость функций и в чем критерий простоты, об этом речь пойдет ниже. Аппроксимация может потребоваться в следующих случаях: 1) известны, например из эксперимента, значения функции (табличное задание функции): 𝑓(𝑥1 ) = 𝑦1 , 𝑓(𝑥2 ) = 𝑦2 , … , 𝑓(𝑥𝑛 ) = 𝑦𝑛 Требуется найти значение функции 𝑓(𝑥 ∗ ), причем значения аргумента 𝑥 ∗ нет среди узлов 𝑥1 , 𝑥2 , … , 𝑥𝑛 . В этом случае можно найти аппроксимирующую функцию 𝑔(𝑥); если она «близка» к 𝑓(𝑥) на множестве узлов 𝑋 = {𝑥1 , 𝑥2 , … , 𝑥𝑛 }, то и в нужной точке 𝑥 ∗ , вероятно, будет выполняться 𝑓(𝑥 ∗ ) ≈ 𝑔(𝑥 ∗ ). 2) функция 𝑓(𝑥) задана аналитически, т.е. формулой, но эта формула слишком сложна для регулярного использования. И в этом случае выгодно аппроксимировать 𝑓(𝑥) более простой функцией 𝑔(𝑥) и все расчеты выполнять с ней. С этой целью чаще всего используются п о л и н о м ы (многочлены) – эти функции самые «простые» и поэтому удобны в качестве аппроксимирующих. 𝑃𝑛 (𝑥) = 𝑎0 + 𝑎1 𝑥 + 𝑎2 𝑥 2 + ⋯ + 𝑎𝑛 𝑥 𝑛 . (1) Действительно, многочлены – самые легко вычислимые функции: их легко складывать, умножать и делить; их можно элементарно дифференцировать и интегрировать. Рассмотрим некоторые подходы к понятию б л и з о с т и функций. 1. Интерполяция. Требуется найти полином 𝑃𝑛 (𝑥), принимающий те же значения, что и аппроксимируемая функция 𝑓(𝑥), в (𝑛 + 1) узле 𝑃𝑛 (𝑥𝑖 ) = 𝑓(𝑥𝑖 ), 𝑖 = 0,1,2, … , 𝑛. Такой полином называется интерполяционным, а точки 𝑥0 , 𝑥1 , … , 𝑥𝑛 − узлами интерполяции. Если число узлов велико, то отыскание интерполяционного полинома будет трудоемким (можно убедиться далее, когда будут рассмотрены формулы для коэффициентов полинома). Кроме того, точное равенство 𝑃𝑛 (𝑥𝑖 ) = 𝑓(𝑥𝑖 ) может оказаться бессмысленным требованием, если сами значения 𝑓(𝑥𝑖 ) аппроксимируемой функции в узлах получены из эксперимента, т.е. заведомо неточно. 2. Наилучшее приближение. Пусть функция 𝑓(𝑥) задана таблично в узлах 𝑥0 , 𝑥1 , … , 𝑥𝑛 . Подберем полином 𝑃𝑛 (𝑥) = 𝑎0 + 𝑎1 𝑥 + 𝑎2 𝑥 2 + ⋯ + 𝑎𝑛 𝑥 𝑛 так, чтобы сумма квадратов разностей значения аппроксимируемой функции и полинома по всем узлам минимизировалась: 𝒏 2 ∑(𝑓(𝑥𝑖 ) − 𝑃𝑛 (𝑥𝑖 )) → 𝑚𝑖𝑛. 𝒊=𝟎 Из данного условия определяются коэффициенты 𝑎0 , 𝑎1 , … , 𝑎𝑛 искомого полинома. Такой путь нахождения полинома приводит к известному методу наименьших квадратов. Но это уводит от понятия интерполяции. При интерполяции для заданной таблично в узлах 𝑥0 , 𝑥1 , … , 𝑥𝑛 функции 𝑓(𝑥) 𝑓(𝑥0 ) = 𝑦0 , 𝑓(𝑥1 ) = 𝑦1 , … , 𝑓(𝑥𝑛 ) = 𝑦𝑛 требуется найти интерполяционный полином, такой, что 𝑃𝑛 (𝑥𝑖 ) = 𝑓(𝑥𝑖 ), 𝑖 = 0,1,2, … , 𝑛. (2) Геометрически это означает, что график полинома проходит через точки 𝑀𝑖 (𝑥𝑖 , 𝑦𝑖 ), 𝑖 = 0,1,2, … , 𝑛. На рисунке изображены графики аппроксимируемой функции и ее интерполяционного полинома (помним, график полинома – ломаная): Интерполяционный полином используется для приближенного вычисления значений функции 𝑓(𝑥) в точке, отличной от узлов интерполяции, 𝑓(𝑥) ≈ 𝑃𝑛 (𝑥𝑖 ). Если значение х лежит между узлами интерполяции, то приближенное отыскание значения 𝑓(𝑥) называется интерполированием (в узком смысле); если же значение х лежит левее или правее всех узлов, то говорят об интерполировании в широком смысле (или экстраполировании). Степень интерполяционного полинома, построенного по (𝑛 + 1) точке, в исключительных случаях может оказаться меньше n. Например, если все точки 𝑀𝑖 (𝑥𝑖 , 𝑦𝑖 ), лежат на одной прямой (наклонной или горизонтальной), то полином будет иметь первую (соответственно нулевую) степень. Понятно, что такие случаи крайне редки. В общем случае по заданным значениям 𝑓(𝑥) в (𝑛 + 1) узле конструируется полином степени n, притом единственным образом. Покажем это. Подставляя в общий вид полинома (1) условия (2), получим систему из (𝑛 + 1) линейного уравнения 𝑎0 + 𝑎1 𝑥0 + 𝑎2 𝑥0 2 + ⋯ + 𝑎𝑛 𝑥0 𝑛 = 𝑦0 𝑎0 + 𝑎1 𝑥1 + 𝑎2 𝑥1 2 + ⋯ + 𝑎𝑛 𝑥1 𝑛 = 𝑦1 ⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯ {𝑎0 + 𝑎1 𝑥𝑛 + 𝑎2 𝑥𝑛 2 + ⋯ + 𝑎𝑛 𝑥𝑛 𝑛 = 𝑦𝑛 В этой системе неизвестные – коэффициенты 𝑎0 , 𝑎1 , … , 𝑎𝑛 . Решение этой системы — коэффициенты интерполяционного полинома 𝑎0 , 𝑎1 , … , 𝑎𝑛 - существует и единственно (в этом убедиться, если для применения метода Крамера вычислить определитель: он не равен 0 ввиду того, что все узлы интерполяции – различные числа). Значит, по заданной в (𝒏 + 𝟏) узле функции 𝒇(𝒙) можно построить интерполяционный полином 𝑷𝒏 (𝒙) степени n, и притом единственным образом. Интерполяционный полином Лагранжа Для системы узлов 𝑥0 , 𝑥1 , … , 𝑥𝑛 введем коэффициенты Лагранжа вида 𝐿𝑖𝑛 (𝑥) = (𝑥 − 𝑥0 ) ∙ (𝑥 − 𝑥1 ) ∙ … ∙ (𝑥 − 𝑥𝑖−1 ) ∙ (𝑥 − 𝑥𝑖+1 ) ∙ … (𝑥 − 𝑥𝑛 ) . (3) (𝑥𝑖 − 𝑥0 ) ∙ (𝑥𝑖 − 𝑥1 ) ∙ … ∙ (𝑥𝑖 − 𝑥𝑖−1 ) ∙ (𝑥𝑖 − 𝑥𝑖+1 ) ∙ … ∙ (𝑥𝑖 − 𝑥𝑛 ) Здесь индекс 𝑖 = 0,1,2, … , 𝑛. В числителе каждый сомножитель представляет собой разность переменного х и значения одного из узлов (за исключением i-го узла, что отмечено верхним индексом в обозначении функции 𝐿𝒊𝑛 ). Знаменатель формально отличается от числителя тем, что вместо переменного х подставлено значение пропущенного, i-го, узла интерполяции − 𝑥𝑖 . Нижний индекс обозначения 𝐿𝑖𝒏 означает получаемую после упрощения степень многочлена 𝐿𝑖𝑛 (𝑥) , равную n (действительно, в числителе именно n скобок, содержащих x). Если в (3) вместо x подставить в числителе значение узла интерполяции 𝑥𝑗 , то получим 1, если 𝑗 = 𝑖 𝐿𝑖𝑛 (𝑥𝑗 ) = { . 0, если 𝑗 ≠ 𝑖 Итак, полином Лагранжа, имеющий вид 𝒏 𝑳𝒏 (𝒙) = ∑ 𝒇(𝒙𝒊 ) ∙ 𝑳𝒊𝒏 (𝒙) = 𝒇(𝒙𝟎 ) ∙ 𝑳𝟎𝒏 (𝒙) + 𝒇(𝒙𝟏 ) ∙ 𝑳𝟏𝒏 (𝒙) + ⋯ + 𝒇(𝒙𝒏 ) ∙ 𝑳𝒏𝒏 (𝒙) (𝟒) 𝒊=𝟎 удовлетворяет условиям (2): 𝐿𝑛 (𝑥𝑖 ) = 𝑓(𝑥𝑖 ), 𝑖 = 0,1,2, … , 𝑛 и имеет степень 𝑛, т.е. является искомым интерполяционным полиномом. Пример. Пусть y = 𝑓(𝑥) задана таблично своими значениями в четырех узлах: i узлы 𝑥𝑖 -1 1 2 2 3 5 𝑦𝑖 = 𝑓(𝑥𝑖 ) 1 -3 2 4 Построим ИП Лагранжа; найдем 𝑓(1) . Тогда Насколько точно полученное значение? Погрешность интерполяции вычисляется следующим образом: (5) Здесь 𝑀𝑛+1 − максимум значений (𝑛 + 1) −й производной на отрезке интерполирования: 𝒎𝒂𝒙 |𝑓 (𝑛+1) (𝒙)| = 𝑴𝑛+1 𝒙∈[𝒂,𝒃] Пример. Функция 𝑓(𝑥) = ln 𝑥 задана таблично своими значениями в узлах 𝑥0 =100 , 𝑥1 =101, 𝑥2 =102 , 𝑥3 =103; по табличным данным построен 𝐿3 (𝑥); его применили для приближенного вычисления ln100,5. Оценить, с какой точностью получается это значение. Итак, требуется оценить погрешность интерполяции 𝑅3 (100,5). По формуле (5) (минимальный отрезок, содержащий все узлы интерполяции – от 100 до 103). Найдем 4-ю производную от ln𝑥: 1 1 ′ 1 1 ′ 2 2 ′ 6 (𝑙𝑛 𝑥) = ; ( ) = − 2 ; (− 2 ) = 3 ; ( 3 ) = − 4 𝑥 𝑥 𝑥 𝑥 𝑥 𝑥 𝑥 ′ ⟹ (𝑙𝑛 𝑥)(4) = − 6 𝑥4 Вычислим максимум полученной производной на отрезке [100; 103]: 𝑀4 = max 𝑥∈[100,103] Оценка погрешности интерполяции: |− 6 6 | = 𝑥4 1004 Вывод: вычисление ln100.5 с помощью интерполяционного полинома Лагранжа 𝐿3 (𝑥) дает ответ с восемью верными десятичными знаками, т. е. очень точный ответ.