1611688847-5b7354cc83380cb6c671f7c9dd5f83f8 (2017- Лекции Шарый)

Вычислительные методыанализа и линейной алгебрыКурс лекцийС.П. ШарыйКафедра математического моделирования НГУЛекция 17 ноября 2017 г.Составные квадратурные формулыСоставная квадратурная формула трапецийСоставные квадратурные формулыПри разбиении интервала интегрирования на N равных частейполную погрешность интегрирования R̃(f ) можно оценить сверхукак|R̃(f )| ≤N−1XC[ri ,ri+1 ]i=0≤ N C[a,b]b−aNb−aNpp=≤N−1Xi=0C[a,b]b−aNpC[a,b] (b − a)p= C[a,b] (b − a)hp−1 .N p−1Составные квадратурные формулыПри разбиении интервала интегрирования на N равных частейполную погрешность интегрирования R̃(f ) можно оценить сверхукак|R̃(f )| ≤N−1XC[ri ,ri+1 ]i=0≤ N C[a,b]b−aNb−aNpp=≤N−1Xi=0C[a,b]b−aNpC[a,b] (b − a)p= C[a,b] (b − a)hp−1 .N p−1Эта погрешность уменьшилась в N p−1 разпо сравнению с погрешностью элементарной квадратуры.Составные квадратурные формулыПри разбиении интервала интегрирования на N равных частейполную погрешность интегрирования R̃(f ) можно оценить сверхукак|R̃(f )| ≤N−1XC[ri ,ri+1 ]i=0≤ N C[a,b]b−aNb−aNpp=≤N−1Xi=0C[a,b]b−aNpC[a,b] (b − a)p= C[a,b] (b − a)hp−1 .N p−1Эта погрешность уменьшилась в N p−1 разпо сравнению с погрешностью элементарной квадратуры.Таким способом погрешность вычисления интеграла в идеалеможно сделать сколь угодно малой.Порядок точности формулы или методаОпределениеСтанем говорить, что приближённая формула или приближённыйчисленный метод имеют p-ый порядок точности (или порядокаппроксимации), если на равномерной сетке с шагом h ихпогрешность является величиной O(hp ), т.

е. не превосходит Chp ,где C — некоторая константа, не зависящая от h.Порядок точности формулы или методаОпределениеСтанем говорить, что приближённая формула или приближённыйчисленный метод имеют p-ый порядок точности (или порядокаппроксимации), если на равномерной сетке с шагом h ихпогрешность является величиной O(hp ), т. е. не превосходит Chp ,где C — некоторая константа, не зависящая от h.Нередко понятие порядка точности распространяют и нанеравномерные сетки, в которых шаг hi меняется от узла к узлу.Тогда роль величины h играет какой-нибудь «характерныйразмер», описывающий данную сетку, например, h = maxi hi .Порядок точности формулы или методаПогрешность формулы средних прямоугольников|R(f )| ≤M2 (b − a)3.24Погрешность формулы трапеций|R(f )| ≤M2 (b − a)3.12Погрешность формулы Симпсона (парабол)|R(f )| ≤M4 (b − a)5.2880Составные квадратурные формулыДля равномерного разбиения интервала интегрирования составныеквадратурные формулы выглядят особенно просто.Выпишем их явный вид для простейших квадратурных формулНьютона-Котеса и разбиения интервала интегрирования [a, b] на Nравных частей[r0 , r1 ],[r1 , r2 ],...,[rN −1 , rN ]длины h = (b − a)/N каждая, в котором a = r0 и rN = b.Составные квадратурные формулыСоставная формула средних прямоугольниковZгде ri−1/2 = ri − h/2.baf (x) dx ≈ hNXi=1f (ri−1/2 ),Составные квадратурные формулыСоставная формула средних прямоугольниковZbaf (x) dx ≈ hNXf (ri−1/2 ),i=1где ri−1/2 = ri − h/2.Её полная погрешность|R̃(f )| ≤ M2(b − a)h2,24т.

е. она имеет второй порядок точности.Эта формула совпадает с интегральной суммой Риманадля интеграла от f (x) по интервалу [a, b].Составные квадратурные формулыСоставная формула трапецийZabN−1X11f (x) dx ≈ h 2 f (a) +f (ri ) + 2 f (b) .i=1Составные квадратурные формулыСоставная формула трапецийZabN−1X11f (x) dx ≈ h 2 f (a) +f (ri ) + 2 f (b) .i=1Её полная погрешность|R̃(f )| ≤ M2т.

е. порядок точности тоже второй.(b − a)h2,12Составные квадратурные формулыСоставная формула Симпсона (формула парабол)Zabf (x) dx ≈где ri−1/2 = ri − h/2.Nh Xf (ri−1 ) + 4f (ri−1/2 ) + f (ri ) ,6i=1Составные квадратурные формулыСоставная формула Симпсона (формула парабол)ZaNh Xf (ri−1 ) + 4f (ri−1/2 ) + f (ri ) ,6bf (x) dx ≈i=1где ri−1/2 = ri − h/2.Её полная погрешность|R̃(f )| ≤ M4(b − a)h4,2880т. е.

формула имеет четвёртый порядок точности.Составные квадратурные формулыНекоторые составные квадратурные формулы обладаютсвойствами, которые качественно превосходят свойстваэлементарных квадратур, на которых они основаны.Составные квадратурные формулыНекоторые составные квадратурные формулы обладаютсвойствами, которые качественно превосходят свойстваэлементарных квадратур, на которых они основаны.Несмотря на свою простоту, квадратурные формулыпрямоугольников обладают замечательным свойствомнаивысшей тригонометрической степени точности.Составные квадратурные формулыНекоторые составные квадратурные формулы обладаютсвойствами, которые качественно превосходят свойстваэлементарных квадратур, на которых они основаны.Несмотря на свою простоту, квадратурные формулыпрямоугольников обладают замечательным свойствомнаивысшей тригонометрической степени точности.Будем рассматривать квадратурную формулу видаZ2π0f (x) dx ≈nXck f (xk ),k=1т.

е. на интервале периода основных тригонометрических функций.Составные квадратурные формулыГоворят, что квадратурная формула имеет тригонометрическуюстепень точности, равную m, если она точна для любоготригонометрического полинома порядка m, т. е. для функцийa0 +mXk=1ak cos kx + bk sin kx ,и не точна для тригонометрических полиномов порядка m + 1.Составные квадратурные формулыГоворят, что квадратурная формула имеет тригонометрическуюстепень точности, равную m, если она точна для любоготригонометрического полинома порядка m, т.

е. для функцийa0 +mXk=1ak cos kx + bk sin kx ,и не точна для тригонометрических полиномов порядка m + 1.ПредложениеТригонометрическая степень точности квадратурной формулы,построенной по n узлам, не превосходит n − 1.Доказательство опускается.Составные квадратурные формулыТеорема И.П. МысовскихСоставная квадратурная формула прямоугольниковZ2π0f (x) dx ≈N2π(k − 1)2π Xf x1 +,NNk=1где x1 — произвольная точка из подинтервала [0, 2π/N ],и только она является квадратурной формулой наивысшейтригонометрической степени точности N − 1.Доказательство теоремы нетривиально, и мы не приводим его.Вычислительные методылинейной алгебрыКакие задачи решает эта наука?Какие задачи решает эта наука?• Решение систем линейных алгебраических уравнений.Какие задачи решает эта наука?• Решение систем линейных алгебраических уравнений.• Линейная задача о наименьших квадратах:для заданных m×n-матрицы A и m-вектора bнайти вектор x, который доставляет минимумквадрату невязки hAx − b, Ax − bi.Какие задачи решает эта наука?• Решение систем линейных алгебраических уравнений.• Линейная задача о наименьших квадратах:для заданных m×n-матрицы A и m-вектора bнайти вектор x, который доставляет минимумквадрату невязки hAx − b, Ax − bi.• Нахождение собственных значений и собственныхвекторов матриц.Какие задачи решает эта наука?• Решение систем линейных алгебраических уравнений.• Линейная задача о наименьших квадратах:для заданных m×n-матрицы A и m-вектора bнайти вектор x, который доставляет минимумквадрату невязки hAx − b, Ax − bi.• Нахождение собственных значений и собственныхвекторов матриц.• Нахождение сингулярных чисел и сингулярныхвекторов матриц.Какие задачи решает эта наука?• Решение систем линейных алгебраических уравнений.• Линейная задача о наименьших квадратах:для заданных m×n-матрицы A и m-вектора bнайти вектор x, который доставляет минимумквадрату невязки hAx − b, Ax − bi.• Нахождение собственных значений и собственныхвекторов матриц.• Нахождение сингулярных чисел и сингулярныхвекторов матриц.• А также некоторые другие не столь популярные задачи .

. .Собственные числаи собственные векторы матрицЕсли λ — собственное значение n × n-матрицы A, а x, x 6= 0,— её собственный вектор, то они удовлетворяют уравнениюAx = λ x,т. е. на одномерном линейном подпространстве, порождённомсобственным вектором x, линейное преобразование, котороезадаётся матрицей A, действует как умножение на λ.(1)Собственные числаи собственные векторы матрицЕсли λ — собственное значение n × n-матрицы A, а x, x 6= 0,— её собственный вектор, то они удовлетворяют уравнениюAx = λ x,(1)т.

е. на одномерном линейном подпространстве, порождённомсобственным вектором x, линейное преобразование, котороезадаётся матрицей A, действует как умножение на λ. Собственныезначения — это корни характеристического уравнения матрицыdet(A − λI) = 0.Для n × n-матрицы A это алгебраическое уравнение n-ой степени, идля его исследования нужно привлекать поле комплексных чисел C.Совокупность собственных чисел матрицы называется её спектром.Собственные векторы x, являющиеся решениями (1), называюттакже правыми собственными векторами, поскольку онисоответствуют умножению на матрицу справа. Но нередковозникает необходимость рассмотрения левых собственныхвекторов, удовлетворяющихy ∗A = µ y ∗для y ∈ Cn и некоторого µ ∈ C.Собственные векторы x, являющиеся решениями (1), называюттакже правыми собственными векторами, поскольку онисоответствуют умножению на матрицу справа.

Но нередковозникает необходимость рассмотрения левых собственныхвекторов, удовлетворяющихy ∗A = µ y ∗для y ∈ Cn и некоторого µ ∈ C.Применяя эрмитово сопряжение, получимA∗ y = µy,т. е. левые собственные векторы матрицы A являются правымисобственными векторами эрмитово сопряжённой матрицы A∗ .Ясно, что det(A∗ − µI) = 0.ПредложениеСобственные значения эрмитово-сопряжённых матриц попарнокомплексно сопряжены друг другу.Доказательство:Известно, что det A⊤ = det A. С другой стороны, det A = det A.Следовательно,det(A − λI) = det(A − λI)⊤ = det(A⊤ − λI)= det A⊤ − λI= det A∗ − λI .ПредложениеСобственные значения эрмитово-сопряжённых матриц попарнокомплексно сопряжены друг другу.Доказательство:Известно, что det A⊤ = det A.

С другой стороны, det A = det A.Следовательно,det(A − λI) = det(A − λI)⊤ = det(A⊤ − λI)= det A⊤ − λI= det A∗ − λI .Отсюда мы можем заключить, что комплексное число z являетсякорнем характеристического уравнения det(A − λI) = 0 дляматрицы A тогда и только тогда, когда ему сопряжённое z являетсякорнем уравнения det(A∗ − λI) = 0, характеристического дляматрицы A∗ .Собственные числаи собственные векторы матрицОбращаясь к определению правых и левых собственных векторовматрицы, можем утверждать, что если λ — правое собственноезначение матрицы A, а µ — левое собственное значение, то λ = µ.Собственные числаи собственные векторы матрицОбращаясь к определению правых и левых собственных векторовматрицы, можем утверждать, что если λ — правое собственноезначение матрицы A, а µ — левое собственное значение, то λ = µ.Иными словами, правые и левые собственные значения матрицысовпадают друг с другом.Собственные числаи собственные векторы матрицОбращаясь к определению правых и левых собственных векторовматрицы, можем утверждать, что если λ — правое собственноезначение матрицы A, а µ — левое собственное значение, то λ = µ.Иными словами, правые и левые собственные значения матрицысовпадают друг с другом.Поэтому их можно не различать и говорить просто о собственныхзначениях матрицы.Сингулярные числаи сингулярные векторы матрицыДля определения собственных значений матрицы A и её левых иправых собственных векторов необходимо решить системууравнений(Ax = λ x,y∗A = λ y∗.(2)Система уравнений (2) является «распавшейся»: в ней перваяполовина уравнений — Ax = λx — никак не зависит от второйполовины уравнений, т.