Вычислительная математика. Лекции

ВЫЧИСЛИТЕЛЬНАЯ МАТЕМАТИКА Лекции для студентов 2-ого курса, 3-ий семестр

Лекции соответствуют программе общефакультетского курса “Вычислительная математика“, читаемого на кафедре Информационных систем факультета ПМ-ПУ. Некоторые доказательства и оценки проведены более подробно, что позволяет лектору отнести их изучение на самомстоятельную работу студентов.

Лекции.(45 часов)

Глава 1. Введение. Методы решения скалярных уравнений. Глава 2. Метод Ньютона решения систем нелинейных уравнений. Глава 3. Решение систем линейных алгебраических уравнений. Глава 4. Методы минимизации значений квадратичной функции. Глава 5. Введение. Интерполирование функций.

Глава 6. Аппроксимация функций.

Вычислительный практикум.(15 часов)

Методические указания по темам вычислительного практикума и зачетные задания разработаны преподавателями кафедры Информационных систем и размещены на сайте этой кафедры.

Основная литература.

1.Бахвалов Н., Жидков Н., Кобельков Г. Численные методы. Изд-во “Бином“ 2003.

2.Вержбицкий В.М. Основы численных методов. “Высшая школа“ Москва, 2002.

3.Крылов В.И., Бобков В.В, Монастырский П.И. Начала теории вычислительных методов. Линейная алгебра и нелинейные уравнения. Минск: Наука и техника, 1982.

4.Крылов В.И., Бобков В.В, Монастырский П.И. Начала теории вычислительных методов. Интерполирование и интегрирование. Минск: Наука и техника, 1984.

Дополнительная литература.

1.Воеводин В.В. Вычислительные основы линейной алгебры. “Наука“, Москва, 1977.

2.Поляк В.Т. Введение в оптимизацию. “Наука“, Москва, 1982.

Доцент, канд. физ.-мат. наук Сергеев Владимир Олегович

2012

ВВЕДЕНИЕ

1. Общая постановка задачи. Задачи, корректно поставленные по Адамару.

Пусть заданы два метрические пространства X и Y и отображение F из X в Y . Требуется найти для заданного y такой элемент x, что

F(x) = y:

В большинстве практических задач не всегда явно предполагается, что искомый элемент x принадлежит некоторому подмножеству X, то есть не любой элемент x, удовлетворяющий уравнению F(x) = y, может быть назван решением задачи. Естественно было бы ограничить и множество элементов y : y 2 F(x): Однако установить принадлежность элемента y этому множеству довольно сложно, к тому же элемент y как правило известен с некоторой погрешностью измерений или произведенных ранее вычислений. Например, если при определении плотности пород, находящихся под поверхностью земли, исходя из измерений гравитационного или магнитного поля на поверхности земли, получены значения плотности 50 г=см3, то такое решение неприемлемо, так как заранее известно, что значения плотности не превышают 20 г=см3.

Итак, для уравнения F(x) = y мы должны прежде всего рассмотреть вопрос о существовании решения задачи в множестве при заданном элементе y.

Пусть для заданного элемента y известно, что решение задачи существует. Второй вопрос: единственно ли это решение? Если решение неединственно, то алгоритм построения решения может и не приводить к определённому результату.

Далее, если решение существует и единственно, то возникает следующий вопрос - вопрос устойчивости этого решения. Пусть элемент y известен с точностью ", то есть расстояние Y (y; y ) между заданным элементом y и точным элементом y , не превосходит ". Если расстояние между соответствующими решениями x" и x стремится к нулю при " ! 0, то говорят, что задача решения уравнения устойчива относительно вариации элемента y . Если отсутствует устойчивость, то требуются специальные методы решения задачи, минимизирующие влияние погрешностей в задании элемента y.

Если для поставленной задачи решения уравнения F(x) = y выполнены условия:

1.решение существует,

2.решение единственно,

3.доказана устойчивость решения,

то говорят, что задача поставлена корректно по Адамару.

2. Погрешности решения задач. Представление приближенных чисел.

Решение корректно поставленной задачи заменяется решением более простой задачи Fe(x) = y . Такая замена определяет метод решения исходной задачи. Обозначая через x и xe решения этих задач, получаем погрешность, которая называется методической погрешностью решения. Она зависит от выбора метода.

Если точное значение элемента y неизвестно, но известно его приближенное значение y, то решения соответствующих задач x и xe определяют неустранимую погрешность. Погрешности вычислительных

процедур, входящих в решение уравнения Fe(x) = y должны быть согласованы с точностью задания элемента y и включаются в методическую погрешность.

1

Сумма методической погрешности и неустранимой погрешности называется полной погрешностью решения задачи.

Пусть число a является приближенным значением величины a : a = a + a. Значение a называется абсолютной погрешностью числа a (в отличие от относительной погрешности jjaajj). Конечно, значение a неизвестно, известна только оценка j aj < a. Величина a называется оценкой абсолютной погрешности числа a.

Пусть число a представлено в десятичной форме:

a = ( 1)[ n10n + n 110n 1 : : : + k10n k + : : : + N 10N ];

где k- цифры, и известна оценка a.

Цифра k называется верной, если a < единицы (или половины единицы) k-го разряда в представлении числа a.

Например: a = 0:009823; a = 0:0002:

Цифра 8(k = 4) неверна, так как 0:0002 > 0:0001. Цифра 9(k = 3) верна: 0:0002 < 0:001.

Все цифры, предшествующие верной цифре, верны.

Округление. Число 0:009823 округляется до числа 0:0010: В этом представлении все цифры верные. После округления в записи числа a следует оставить только верные цифры: a = 0:0010:

Пусть k- первая верная цифра, отличная от 0. Все последующие верные цифры называются значащими.

В примере цифры 1; 0 - значащие цифры. Особенно важно правильное представление приближенных значений чисел в конечных результатах. Например: правильное представление числа x = 3:14158254358 при

x = 0:0001 : x = 3:1416:

3. Погрешности вычисления значений функции многих переменных.

Пусть при вычислении значений функции f(x1; x2; : : : ; xn) значения аргументов xi известны с абсолют-

ной погрешностью xi:

xi = xi + xi; x = x + x:

Будем предполагать, что в окрестности точки x функция f(x) дифференцируема:

n

Ясно, что f P Bi xi, где Bi = maxj@f(x) j в окрестности точки x .

i=1

@xi

Таким образом, зная величины Bi и оценки абсолютных погрешностей xi, получаем оценку f абсолютной погрешности вычисления значений функции f(x):

Обратная задача. Задана оценка " погрешности вычисления значений функции f(x): Требуется определить погрешность xi задания аргументов xi.

Первый способ: все значения xi равны: xi = ,

n

Второй способ (метод равных влияний): все значения величин Bi xi равны: Bi xi = "0. Тогда " = "0n, "0 = n" и оценки абсолютных величин погрешностей равны xi = nB" i :

2

Глава 1

МЕТОДЫ РЕШЕНИЯ СКАЛЯРНЫХ УРАВНЕНИЙ.

1.1Метод Чебышева.

Постановка задачи. Пусть на [a; b] задана непрерывная функция F(x): Требуется найти значения x 2 [a; b], в которых F(x) = 0: Если значения функции F в точках a и b имеют противоположные знаки, то решение задачи существует. Единственность решения обеспечивается требованием строгой монотонности функции F(x). Если далее предположить, что функция F(x) дифференцируема и jF0(x)j > 0, то задача решения уравнения F(x) = 0 поставлена корректно по Адамару.

Будем предполагать, что все эти условия выполнены для x 2 [a; b]: Тогда существует обратная функция(y), заданная для значений y, лежащих между значениями F(a) и F(b):

(F(x)) x для x 2 [a; b]:

Обратная функция имеет столько же непрерывных производных, сколько и функция F(x):

В методе Чебышева дополнительно предполагается, что функция F имеет на [a; b] (m+1) непрерывных производных.

Построение метода.

Взяв произвольное значение y0 из области задания функции , получаем по формуле Тейлора

k=1

Значение y0 определим, выбрав произвольно значение x0 2 [a; b] и положив y0 = F (x0): Тогда

k=1

Тогда

x = x1 + rm+1(y0):

Далее взяв в качестве y1 = F(x1), получаем

3

в надежде, что все значения xn 2 [a; b] и что xn ! x при n ! 1: Ясно, что jx xn+1j jrm+1(yn)j:

Этот итерационный метод построения числовой последовательности fxng и называется методом Чебы-

Продолжая процесс дифференцирования тождества, получаем последовательно формулы для вычис-

dk (F(x))

ления dyk :

Вчастном случае при m = 1 метод Чебышева называется методом Ньютона.

Вэтом методе

xn+1 = xn F0(xn) или F(xn) + F0(xn)(xn+1 xn) = 0:

F (xn)

Рассмотрим уравнение касательной к графику функции F(x) в точке xn : y = F(xn) + F0(xn)(x xn): Координата точки пересечения этой прямой с осью x равна xn+1.

Уже для метода Ньютона легко построить примеры, когда xn не стремится к x : метод может “зацикливаться”, т.е. начиная с некоторого N xN+2 = xN

1.2Порядок сходимости метода Чебышева.

Предположим, что все xn 2 [a; b] и что xn ! x при n ! 1: По формуле Тейлора

4

jx xn+1j C0jx xnjm+1:

Терминология. Пусть построена последовательность элементов xn такая что xn ! x . Если

k x xn+1 k C0 k x xn kN ;

то говорят, что порядок сходимости равен N: В частности:

-если N = 1, то говорят, что метод построения последовательности fxng - метод первого порядка,

-если N > 1, то говорят о сверхлинейной сходимости,

-если N = 2, то получаем метод второго порядка.

Метод Чебышева имеет порядок (m + 1), метод Ньютона - метод второго порядка.

Условия принадлежности xn отрезку [a; b] и условия сходимости метода Чебышева в общем случае трудно проверяемы. Для метода Ньютона эти условия будут получены в следующей главе для более общего случая систем нелинейных уравнений.

1.3Метод простой итерации решения скалярного уравнения x = f(x).

Вэтом случае F(x) = x f(x): Решения уравнения f(x) = x называются неподвижными точками функции f:

Конечно, можно применить метод Чебышева, но тогда придется вычислять значения производных функции f, что во многих случаях довольно сложно. В предлагаемом методе не требуется вычисления производных.

Метод простой итерации состоит в выборе начального приближения x0, а все последующие приближе-

ния x1; x2; : : : вычисляются последовательно правилу: xn+1 = f(xn):

Каковы перспективы этого метода? Простые примеры показывают, что если jf0(x)j 1, то метод простой итерации расходится. В дальнейшем ограничение на f0(x) заменяется на более слабое условие.

Пусть в окрестности точки x0:jx x0j выполнены условия: - функция f задана в области ,

в области функция f(x) удовлетворяет условию Липшица с постоянной L < 1 : jf(x00) f(x0)j < L[x00 x0] для любых точек x00 и x0 области ,

- значение m = jf(x1) f(x0)j = jx1 x0j не превосходит : m и следовательно точка x1 2 . Найдем соотношения между величинами ; L и m, гарантирующие принадлежность всех xn области

, существование неподвижной точки x функции f в области и сходимость xn ! x :

Оценим jx2 x1j = jf(x1) f(x0)j < Ljx1 x0j = Lm и оценим jx2 x0j jx2 x1j+jx1 x0j Lm+m = (L + 1)m. Потребуем, чтобы (L + 1)m ; тогда x2 2 :

Легко показать, что если jxn xn 1j Ln 1m и jxn x0j (1 + L + L2 + : : : + Ln 2 + Ln 1)m; то jxn+1 xnj Lnm; jxn+1 x0j (1 + L + : : : + Ln 1 + Ln)m < 1 1L m:

Таким образом, если для чисел m; и L выполнено неравенство m < (1 L) ;

5

то все xn 2 . Оценим

jxn+k xnj jxn+k xn+k 1j + jxn+k 1 xn+k 2j + : : : + jxn+1 xnj Ln 1 mL:

Тогда при n ! 1 jxn+k xnj ! 0 и последовательность fxng сходится в себе. В силу полноты про-

странства R1 (признак Коши) существует предел последовательности xn ! x при n ! 1: Так как все xn 2 , то и x 2 .

Из непрерывности функции f получаем f(x ) = lim f(xn) = lim xn 1 = x , следовательно точка x -

n!1 n!1

неподвижная точка функции f(x), принадлежащая области .

Легко убедиться, что x - единственная неподвижная точка: если x2 и x1 - две неподвижные точки, то jx2 x1j = jf(x2) f(x1)j Ljx2 x1j и если x2 6= x1, то L 1:

Таким образом верна

Теорема. Пусть в области : jx x0j < функция f(x) задана и удовлетворяет условию Липшица с

постоянной L < 1.

Если m < (1 L); где m = jf(x0) x0j; то все xn 2 и метод простой итерации сходится к единственной неподвижной точке x 2 и верна оценка

jxn x j 1 mLLn:

Последняя оценка получена предельным переходом в неравенстве

jxn+k xnj 1mL Ln при k ! 1:

Терминология. Если для итерационного метода получена оценка:

k xn x k Cqn; 0 < q < 1;

то xn ! x , и говорят что метод сходится со скоростью геометрической прогрессии со знаменателем q. В условиях доказанной теоремы метод простой итерации сходится со скоростью геометрической про-

грессии со знаменателем L:

6

Глава 2

МЕТОД НЬЮТОНА РЕШЕНИЯ СИСТЕМ НЕЛИНЕЙНЫХ УРАВНЕНИЙ.

Рассматривается система n нелинейных уравнений

8

>f1(x1; x2; :::; xn) = 0

>

<f2(x1; x2; :::; xn) = 0

:: : : : : : : : : : : : : : : : : : : :

>

>

:fn(x1; x2; :::; xn) = 0

относительно неизвестных x(x1; x2; : : : ; xn) 2 Rn: Мы не будем различать точки x 2 Rn и векторы x 2 Vn. Введем вектор-функцию y = F (x) :

yi = fi(x1; x2; : : : ; xn); i = 1; 2; : : : ; n:

Тогда систему уравнений можно записать в виде F (x) = 0:

Метод Ньютона основан на представлении каждой функции fi(x) в виде

оператор F 0(x0), получим представление вектор-функции F (x) в виде:

F (x) = F (x0) + F 0(x0)(x x0) + r(x; x0):

Для предполагаемого решения x системы получаем

F (x0) = F 0(x0)(x x0) + r(x ; x0) = 0:

Пренебрегая вектором r(x ; x0); получаем "приближенное"решение x1 системы как решение системы линейных

Далее строится вектор x2 как решение СЛАУ

F 0(x1)(x x1) = F (x1)

7