Методичка (Г.А. Кокотушкин, А.А. Федотов, П.В. Храпов - Численные методы алгебры и приближения функций)

Московский государственный технический университетимени Н.Э. БауманаГ.А. Кокотушкин, А.А. Федотов,П.В. ХраповЧИСЛЕННЫЕ МЕТОДЫ АЛГЕБРЫИ ПРИБЛИЖЕНИЯ ФУНКЦИЙИздательство МГТУ им. Н.Э. БауманаМосковский государственный технический университетимени Н.Э. БауманаГ.А.

Кокотушкин, А.А. Федотов, П.В. ХраповЧИСЛЕННЫЕ МЕТОДЫ АЛГЕБРЫИ ПРИБЛИЖЕНИЯ ФУНКЦИЙМетодические указанияк выполнению лабораторных работпо курсу «Численные методы»МоскваИздательство МГТУ им. Н.Э. Баумана2011УДК 518.12ББК 22.193К59Р е ц е н з е н т В.Ю. ЧуевК59Кокотушкин Г.А.Численные методы алгебры и приближения функций :метод. указания к выполнению лабораторных работ по курсу«Численные методы» / Г.А. Кокотушкин, А.А. Федотов,П.В. Храпов. — М.: Изд-во МГТУ им. Н.Э.

Баумана, 2011. —58, [2] c. : ил.Рассмотрены численные методы решения систем линейныхалгебраических уравнений (метод Гаусса, LU-разложение, методквадратного корня, метод прогонки), систем нелинейных уравнений(метод простых итераций, метод Ньютона) и методы приближенияфункций (интерполяционные многочлены, интерполяция сплайнами,метод наименьших квадратов). Приведены варианты индивидуальных заданий к лабораторным работам.Для студентов 2-го курса факультетов МТ и РК МГТУим. Н.Э. Баумана. Пособие может быть использовано студентамидругих факультетов.Методические указания рекомендованы Учебно-методическойкомиссией НУК ФН.УДК 518.12ББК 22.193© МГТУ им. Н.Э.

Баумана, 2011ПРЕДИСЛОВИЕПособие содержит теоретический материал и варианты заданий к лабораторным работам по разделам «Численные методы алгебры» и «Приближение функций» курса «Численные методы».Глава 1 посвящена изучению методов решения систем линейных уравнений. Определяются различные нормированные пространства, вводятся и обсуждаются понятия нормы матрицы, устойчивости системы линейных алгебраических уравнений. Даетсяалгоритм степенного метода, рассматривается его применение длянахождения меры обусловленности симметричных матриц. Излагаются метод Гаусса, метод Гаусса с выбором главного элемента,алгоритм LU-разложения, метод квадратного корня, метод прогонки для решения трехдиагональной системы линейных алгебраических уравнений, численные методы решения систем нелинейныхуравнений: метод простых итераций и метод Ньютона.В главе 2 представлены численные методы интерполяции.

Рассматривается интерполяционный многочлен Лагранжа, даетсяоценка его погрешности. Изучаются сплайн-интерполяция и методнаименьших квадратов.Приведены варианты индивидуальных заданий к лабораторным работам.Для студентов 2-го курса факультетов МТ и РК МГТУим. Н.Э. Баумана. Пособие может быть использовано студентамидругих факультетов.31. ЧИСЛЕННЫЕ МЕТОДЫ АЛГЕБРЫ1.1.

Устойчивость системылинейных алгебраических уравненийНормированные пространства. Свойства нормы матрицыОпределение. Нормированным пространством называется линейное пространство L, в котором для любого элемента x ∈ L определен функционал x (норма х), такой, что выполняются условия:1) x ≥ 0, причем x = 0 ⇔ x = 0;2) λx = λ ⋅ x , ∀λ ∈ R;3) x + y ≤ x + y , ∀x, y ∈ L.Пример 1.

Рассмотрим пространство R1. Здесьx = x,x+ y ≤ x + y .Пример 2. ПустьR1n — n-мерное пространство. Здесьnx = ∑ xi , x = ( x1 , x2 ,..., xn ). Проверим выполнение условия 3:i =1nni =1i =1x + y 1 = ∑ xi + yi ≤ ∑ ( xi + yi ) = x 1 + y 1 .Пример 3. Пусть R2n — n-мерное евклидово пространство,x42=n∑ xii =12— евклидова норма.В общем случае равенство x = ( x, x ) определяет норму вевклидовом пространстве.Пример 4. Пусть R∞n — n-мерное пространство с нормойx∞= max xi .i =1,..., nПроверим выполнение условия 3 в определении нормированного пространства:x + y = max xi + yi ≤ max ( xi + yi ) ≤ max xi + max yi = xi =1,..., ni =1,...,ni =1,..., ni =1,..., n∞+ y∞.Пример 5. Пусть C[a,b] — пространство непрерывных на [a,b]функций; f = max f (t ) .t ∈[ a , b ]Докажем выполнение условия 3 в определении нормированного пространства:f + g = max f (t ) + g (t ) ≤ max ( f (t ) + g (t ) ) ≤t∈[ a ,b ]t∈[ a ,b ]≤ max f (t ) + max g (t ) = f + g .t∈[ a ,b ]t∈[ a ,b ]Пример 6.

Пусть R pn — n-мерное пространство с нормой1/ p⎛ np ⎞x p = ⎜ ∑ xi ⎟ , p ≥ 1.⎝ i =1⎠Пример 7. Рассмотрим пространство матриц вида⎛ a11 a12⎜a21 a22A=⎜⎜ ... ...⎜⎝ an1 an 2... a1n ⎞⎟... a2n ⎟.... ... ⎟⎟... ann ⎠Введем норму матрицы А:A = supx ≠0Axx= sup Ay , посколькуy =1⎛ x ⎞= A⎜,⎜ x ⎟⎟x⎝⎠Ax⎛ x ⎞⎜⎜⎟⎟ = 1.⎝ x ⎠5Пример 8. Пусть A : R22 → R22 , отображение задается матрицей⎛4 0⎞A=⎜⎟ . Параметризуем окружность единичного радиуса:⎝0 1⎠⎧ x1 = cos t , ⎧ y1 = 4 cos t ,⎨⎨⎩ x2 = sin t , ⎩ y2 = sin t.Тогда, как это видно на рис. 1.1.1, A = 4.В общем случае, если А — симметричная матрица, λ1, λ2, λ3,…, λn — ее собственные числа, то евклидова норма A = max λ i .i =1,..., nабРис.

1.1.1. Иллюстрация понятия нормы в двумерном евклидовом пространстве:а — окружность единичного радиуса; б — ее образРассмотрим свойства нормы матрицы:1) A + B ≤ A + B ;2) AB ≤ A ⋅ B .Для доказательства свойств 1 и 2 нам понадобится следующееутверждение.6Утверждение. Имеет место неравенство Ax ≤ A ⋅ x .Из определения нормы матрицыAxx≤ A.Отсюда следует утверждение.Докажем свойства нормы матрицы.1. Запишем цепочку неравенств( A + B) x = Ax + Bx ≤ Ax + Bx ≤ A ⋅ x + B ⋅ x .Поделим все части неравенств на x :( A + B) xx≤ A + B ⇒ A+ B ≤ A + B .2) Аналогично( AB ) x = A( Bx) ≤ A ⋅ Bx ≤ A ⋅ B ⋅ x .Осталось поделить все части равенств на x .Пример 9. Пусть A : R n → R n , xAx∞n∑ aij ⋅x ji =1,..., n= maxnj =1n∑ aiji =1,..., n= max= max | xi | .

Тогдаi =1,...,n≤j =1∑ aiji =1,..., n≤ max∞j =1,..., n⋅ xj =1∞⇒ An∑ aiji =1,..., n⋅ x j ≤ max x j ⋅ max∞=j =1n∑ aij .i =1,..., n≤ maxj =1На самом делеAn∞= max ∑ aij ;i =1,..., nj =1nA 1 = max ∑ aij .j =1,..., ni =17Если⎛ 9 1⎞A=⎜⎟ , то A ∞ = 10,⎝ 9 1⎠A 1 = 18 .Устойчивость системылинейных алгебраических уравненийСистема устойчива, если при небольшом изменении входныхданных изменения решения будут небольшими.

ПустьAx = f , где A = (aij ) mxm .Тогда( A + δA)( x + δx ) = f + δf ,где δA — погрешность матрицы коэффициентов A; δx — погрешность решения x; δf — погрешность правой части f уравнения.Если δf = 0, то рассматривают коэффициентную устойчивость.Если δA = 0, то рассматривают устойчивость по правой части.Определение.

Система линейных алгебраических уравненийустойчива, если существует константа C > 0, такая, чтоδx ≤ C ⋅ δf .Далее будем предполагать, что δA = 0, т. е. рассматривать устойчивость по правой части. ТогдаAδx = δf ; δx = A−1δf .Отсюдаδxδfxf=A−1δf ⋅ Axx ⋅ δf=A−1δfAxδfx≤ A ⋅ A−1 = ν ( A),где ν( A) — мера обусловленности матрицы A.8Имеет место неравенство{}ν( A) ≥ 1 1 = E = A ⋅ A−1 ≤ A ⋅ A−1 = ν( A) .Если ν( A)1, то матрица А — плохо обусловлена, т. е.

неболь-шие изменения в правой части (норма δf мала) могут привести ксущественным изменениям решения.Пример. Рассмотрим систему линейных алгебраических уравнений0 ⎞ ⎛ x1 ⎞ ⎛ 1000 ⎞⎛ 1000⎜⎟⎜ ⎟ = ⎜⎟.0, 001⎠ ⎝ x2 ⎠ ⎝ 0, 001⎠⎝ 0Ее решение x1 = 1; x2 = 1. При этом x∞= 1 . Сделаем небольшое(по норме) изменение правой части:δf1 = 0,1; δf 2 = 0,1;δf∞= 0,1.Тогда0 ⎞ ⎛ δx1 ⎞ ⎛ 0,1⎞⎛ 1000⎟ = ⎜ ⎟.⎜⎟⎜0, 001⎠ ⎝ δx2 ⎠ ⎝ 0,1⎠⎝ 0Получимδx1 = 0,0001;δx2 = 100;δx∞= 100.При этом0 ⎞⎛ 0,001A −1 = ⎜⎟;1000 ⎠⎝ 0A ∞ = 1000;A−1∞= 1000;ν( A) = 1000 ⋅1000 = 1000000.9В общем случае имеет место следующая теорема.Теорема. Если δA < A−1δxx≤−1, то⎛ δfδA ⎞⎜⎟.+δA ⎜ fA ⎟1 − ν( A)⎝⎠Aν ( A)Степенной методСтепенной метод позволяет найти наибольшее по модулю собственное значение и собственный вектор квадратной матрицы A.Пусть λ1 , λ 2 ,..., λ m — собственные числа матрицы A.

Для определенности предположим, что λ1 > λ 2 > ... > λ m . При этом собственному значению λ i соответствует собственное подпространство(не обязательно одномерное) с базисом ei ,1 , ei ,2 ,..., ei , ki . Возьмемпроизвольный ненулевой вектор x 0 = ( x10 , x20 ,..., xn0 ) . Разложим егопо базису из собственных векторов { ei ,k }, i = 1, 2, …, m,k = 1, …, ki, где ki — размерность i-го собственного подпространства, соответствующего собственному значению λ i .

Тогдаx 0 = c1,1e1,1 + c1,2e1,2 + ... + c1, k1 e1, k1 + c2,1e2,1 ++ cm ,1em,1 + ... + cm , km em, km .Отсюда следуетAx 0 = λ1c1,1e1,1 + λ1c1,2e1,2 + ... + λ1c1, k1 e1, k1 + λ 2c2,1e2,1 + ...... + λ m cm ,1em ,1 + ... + λ m cm, km em, km ,…,A p x 0 = λ1p c1,1e1,1 + λ1p c1,2e1,2 + ... + λ1p c1, k1 e1, k1 + λ 2p c2,1e2,1 + ...... + λ mp cm ,1em ,1 + ...