Главная страница
Навигация по странице:

  • Верхняя треугольная матрица

  • Нижняя треугольная матрица

  • Вы́рожденная ма́трица

  • Методы обращения матриц

  • ЧМ_Билеты. 1. Основные характеристики численных методов. Взаимосвязь характеристик


    Скачать 1.85 Mb.
    Название1. Основные характеристики численных методов. Взаимосвязь характеристик
    Дата26.02.2018
    Размер1.85 Mb.
    Формат файлаpdf
    Имя файлаЧМ_Билеты.pdf
    ТипДокументы
    #37249
    страница3 из 5
    1   2   3   4   5
    Обобщенная регрессия
    Линейная регрессия предназначена для определения коэффициентов линейной функции y=ax+b, которая наилучшим образом приближает экспериментальные данные.
    Задача обобщенной линейной регрессии – ответить на следующий вопрос: какие значения должны принимать коэффициенты a
    0
    , a
    1
    , ..., a
    N
    , чтобы функция F(x), являющаяся линейным сочетанием N+1 произвольной функции f
    0
    (x), f
    1
    (x), ..., f
    N
    (x) (то есть F(x)=a
    0
    f
    0
    (x)+a
    1
    f
    1
    (x)+...+a
    N
    f
    N
    (x)), проходила между экспериментальными точками так, чтобы сумма квадратов расстояний от точек и до кривой F(x) была минимальной?

    31
    Формулу для расчета обобщенной линейной регрессии:
    C
    1
    f
    1
    (x) + C
    2
    f
    2
    (x) +… + . . . , где f
    N
    (x) – любые функции пользователя, a C
    N
    – подлежащие определению коэффициенты
    16.
    Задаваемая и фактическая ошибки при вычислении значения
    интеграла. Зависимость фактической ошибки от шага интегрирования и
    задаваемой ошибки. Затраты машинного времени.
    Краткие сведения
    Для вычисления определенного интеграла используется формула Ньютона-
    Лейбница если первообразная
    )
    (x
    F
    может быть найдена или не является слишком громоздкой:
    ).
    (
    )
    (
    )
    (
    a
    F
    b
    F
    dx
    x
    f
    b
    a



    В противном случае вычисляют приближенное значение интеграла по квадратурной формуле




    b
    a
    n
    i
    i
    i
    x
    f
    A
    dx
    x
    f
    1
    )
    (
    )
    (
     содержащей
    1 2 
    n
    параметров ( n абсцисс
    i
    x
    , n коэффициентов
    i
    A
    и число узлов), которые нужно выбрать так чтобы формула давала достаточно малую погрешность для широкого класса функций
    )
    (x
    f
    . Очевидно чем больше n , тем выше точность
    Указанному требованию удовлетворяют квадратурные формулы Ньютона-Котеса и квадратурная формула Гаусса
    Пусть шаг интегрирования h = const,
    — вычисленное с шагом h приближение к I.
    Если, далее вычислено также приближенное значение с шагом то в качестве приближенной оценки погрешности последнего вычисленного значения можно рассматривать величину

    32
    На практике, при необходимости вычислить результат с требуемой точностью вычисления повторяются с последовательно уменьшающимся (вдвое) шагом до тех пор, пока не выполнится условие
    Рис.7.1 – алгоритм получения зависимости фактической ошибки интегрирования функции по формуле прямоугольников от шага интегрирования
    начало
    b
    a,
    )
    (
    )
    (
    a
    F
    b
    F
    s


    20
    )
    1
    (
    1

    k
    0
    ,



    y
    k
    a
    b
    h
    h
    x
    b
    x
    h
    a
    x




    ,
    ,
    2
    /

    )
    (x
    f
    y


    x
    h
    y
    *
    h
    y
    s
    ,

    k
    конец

    33
    17.
    Алгоритмы формирования матриц (верхней и нижней треугольных,
    неособенной и особенной).
    Рис.7.7 – адаптивный алгоритм получения зависимостей фактической ошибки и временных затрат при интегрировании функции по формуле прямоугольников от задаваемой ошибки
    начало
    b
    a,
    )
    (
    )
    (
    a
    F
    b
    F
    s


    10
    *
    ;
    011 0
    ;
    10 5







    0
    ,



    ys
    a
    b
    h
    h
    x
    b
    x
    t
    y
    h
    a
    x






    ;
    ;
    0
    ,
    0
    ,
    2
    /





    t
    x
    f
    y
    ),
    (
    x
    h
    y
    *
    t
    y
    s
    ,
    , 


    конец



    y
    ys
    y
    2
    /
    h
    h
    y
    ys


    да

    34
    Верхняя
    треугольная
    матрица (или верхнетреугольная
    матрица) — квадратная матрица , у которой все элементы ниже главной диагонали равны нулю:
    Нижняя треугольная матрица (или нижнетреугольная матрица) -квадратная матрица , у которой все элементы выше главной диагонали равны нулю:
    Невырожденная матрица (иначе неособенная матрица) ― квадратная матрица, определитель которой отличен от нуля. В противном случае матрица называется вырожденной.
    Для квадратной матрицы M над полем невырожденность эквивалентна каждому из следующих условий:

    M обратима, то есть существует обратная матрица;

    строки (столбцы) матрицы M линейно независимы;

    ранг матрицы равен её размерности.
    Вы́рожденная
    ма́трица (синонимы: сингуля́рная
    ма́трица, осо́бая
    ма́трица, осо́бенная
    ма́трица) — квадратная матрица A определитель которой равен нулю.

    35
    начало
    )
    1
    )(
    1
    (
    0
    )
    1
    )(
    1
    (
    0




    n
    j
    n
    i
    j
    i 
    ()
    rand
    l
    ij

    0
    
    ij
    l
    ()
    rand
    u
    ij

    0
    
    ij
    u
    0
    ()


    ij
    ij
    u
    rand
    l
    j
    i
    ()
    0
    rand
    u
    l
    ij
    ij


    i
    j,
    )
    1
    )(
    1
    (
    0
    ),
    1
    )(
    1
    (
    0
    ,




    n
    j
    n
    i
    l
    ij
    да
    да
    )
    1
    )(
    1
    (
    0
    ),
    1
    )(
    1
    (
    0
    ,




    n
    j
    n
    i
    u
    ij
    конец
    1




    n
    n
    u
    l
    )
    1
    )(
    1
    (
    0


    n
    i
    ii
    n
    ii
    n
    u
    u
    l
    l




    *
    ,
    *
    i
    n
    n
    u
    l

     ,



    матрицы
    й
    треугольно
    нижней
    вывод



    матрицы
    й
    треугольно
    верхней
    вывод



    лей
    определите
    вывод
    да
    да
    Рис.3.1 – алгоритм формирования нижней и верхней треугольных матриц с ненулевыми элементами на главных диагоналях

    36
    18.
    Разложение неособенной матрицы в произведение треугольных
    матриц. Алгоритм. Характеристики разложения.
    Рис.3.2 – алгоритм формирования неособенной квадратной матрицы как произведение нижней и верхней треугольных матриц с ненулевыми элементами на главных диагоналях
    начало
    )
    1
    )(
    1
    (
    0
    ),
    1
    )(
    1
    (
    0
    ,




    n
    j
    n
    i
    l
    ij
    )
    1
    )(
    1
    (
    0
    ),
    1
    )(
    1
    (
    0
    ,




    n
    j
    n
    i
    u
    ij
    0

    ij
    a
    )
    1
    )(
    1
    (
    0


    n
    i
    )
    1
    )(
    1
    (
    0


    n
    j
    )
    1
    )(
    1
    (
    0


    n
    k
    kj
    ik
    ij
    u
    l
    a
    *


    i
    j
    k
    ,
    ,
    )
    1
    )(
    1
    (
    0
    ),
    1
    )(
    1
    (
    0
    ,




    n
    j
    n
    i
    a
    ij
    конец





    матрицы
    й
    треугольно
    верхней
    ввод



    матрицы
    квадратной
    й
    неособенно
    вывод





    матрицы
    й
    треугольно
    нижней
    ввод

    37
    Выше было указано, что всякую квадратную матрицу A имеющую отличные от нуля главные диагональные миноры
    ;
    0 11 1



    a
    ;
    0 22 21 12 11 2



    a
    a
    a
    a
    ….;
    ,
    0



    A
    n
    можно представить в виде произведения двух треугольных матриц (верхней и нижней) причем это разложение будет единственным если зафиксировать диагональные элементы одной из матриц (например принять их равными 1). Следовательно,
    U
    L
    A
    *

    , где
    L и U – нижняя и верхняя треугольные матрицы соответственно.
    Для разработки алгоритма необходимо получить формулы, позволяющие вычислять элементы нижней и верхней треугольных матриц по известным значениям элементов исходной матрицы A.
    При
    4

    n
    из произведения матриц
    A
    U
    L

    *
    имеем:
    ,
    43 33 43 23 42 13 41
    a
    u
    l
    u
    l
    u
    l



    ,
    33 33 33 23 32 13 31
    a
    u
    l
    u
    l
    u
    l



    34 34 33 24 32 14 31
    a
    u
    l
    u
    l
    u
    l



    Распространив эти формулы на общий случай ( n - произвольное), получим формулы для вычисления элементов матрицы L :
    ...,
    ,
    2
    ,
    1
    ,
    1
    n
    i
    l
    ii










    1 1
    1
    ...,
    ,
    2
    ,
    1
    ;
    ...,
    ,
    3
    ,
    2
    ,
    /
    )
    (
    j
    k
    jj
    kj
    ik
    ij
    ij
    i
    j
    n
    i
    u
    u
    l
    a
    l
    и формулы для вычисления элементов матрицы U :






    1 1
    ...,
    ,
    2
    ,
    1
    ,
    j
    k
    kj
    jk
    jj
    jj
    n
    j
    u
    l
    a
    u









    1 1
    ...,
    ,
    1
    ;
    1
    ...,
    ,
    2
    ,
    1
    ,
    i
    k
    kj
    ik
    ij
    ij
    n
    i
    j
    n
    i
    u
    l
    a
    u
    Полученные формулы позволяют построить алгоритм разложения неособенной квадратной матрицы в произведение двух треугольных матриц: верхней и нижней с

    38 единичной главной диагональю
    (рис.3.3).
    Рис.3.3 – алгоритм разложения неособенной квадратной матрицы в произведение двух треугольных матриц: верхней и нижней с единичной главной диагональю
    начало
    )
    1
    )(
    1
    (
    0
    ),
    1
    )(
    1
    (
    0
    ,




    n
    j
    n
    i
    a
    ij
    )
    1
    )(
    1
    (
    0


    n
    i
    1

    ii
    l
    )
    1
    )(
    1
    (
    0


    n
    j
    j
    i
    0
    ,
    0

    b
    u
    ij
    )
    1
    )(
    1
    (
    0


    j
    k
    kj
    ik
    u
    l
    b
    *


    да
    k
    jj
    ij
    ij
    u
    b
    a
    l


    j
    i 
    0

    c
    0
    ,
    0


    d
    l
    ij
    да
    )
    1
    )(
    1
    (
    0


    j
    k
    kj
    jk
    u
    l
    c
    *


    k
    c
    a
    u
    jj
    jj


    )
    1
    )(
    1
    (
    0


    i
    k
    kj
    ik
    u
    l
    d
    *


    k
    d
    a
    u
    ij
    ij


    i
    j,
    )
    1
    )(
    1
    (
    0
    ),
    1
    )(
    1
    (
    0
    ,




    n
    j
    n
    i
    l
    ij
    )
    1
    )(
    1
    (
    0
    ),
    1
    )(
    1
    (
    0
    ,




    n
    j
    n
    i
    u
    ij
    конец








    матрицы
    квадратной
    й
    неособенно
    исходной
    ввод





    матрицы
    й
    треугольно
    нижней
    вывод





    матрицы
    й
    треугольно
    верхней
    вывод

    39
    19.
    Методы обращения матриц. Характеристики обращения.
    Методы обращения матриц
    Могут быть обращены только неособенные квадратные матрицы
    Метод окаймления (деления на клетки)
    Исходную матрицу M размера
    n
    n  разобьем на четыре клетки







    d
    c
    b
    a
    M
     где
    d
    c
    b
    a
    ,
    ,
    ,
    – подматрицы размеров
    q
    q
    p
    q
    q
    p
    p
    p




    ,
    ,
    ,
     Примем что матрица
    1

    M
    существует и может быть разбита на клетки так же как и матрица M  те








    D
    C
    B
    A
    M
    1
     где
    D
    C
    B
    A
    ,
    ,
    ,
    – подматрицы размеров
    q
    q
    p
    q
    q
    p
    p
    p




    ,
    ,
    ,

    Поскольку
    E
    MM

    1
    , то






    d
    c
    b
    a
    *






    D
    C
    B
    A
    =






    q
    p
    E
    E
    0 0
     или
    ,
    0
    ,
    0
    ,
    q
    p
    E
    dD
    cB
    dC
    cA
    bD
    aB
    E
    bC
    aA








    Пусть подматрица d имеет обратную
    1

    d  которая известна Тогда после небольших преобразований получим формулы которые могут быть последовательно решены относительно матриц
    D
    C
    B
    A
    ,
    ,
    ,
    :


    ,
    ,
    ,
    1 1
    1 1
    1 1
    cB
    d
    d
    D
    cA
    d
    C
    Abd
    B
    c
    bd
    a
    A














    (*)
    Вычисление обратной матрицы реализуется с помощью метода окаймления Суть его заключается в следующем Пусть дана матрица











    nn
    n
    n
    m
    m
    m
    m
    M
    1 1
    11

    Образуем
     
    11 1
    m
    M
    ;







    22 21 12 1
    2
    m
    m
    m
    M
    M
    ;











    33 32 31 23 13 2
    3
    m
    m
    m
    m
    m
    M
    M
    и тд

    40
    Каждая следующая матрица получена из предыдущей при помощи окаймления
    Обратная к первой из этих матриц находится непосредственно:
    11 1
    1 1 m
    M


     Зная
    1 1

    M и применив к
    2
    M
    схему вычислений (*) можно получить
    1 2

    M  а затем при помощи
    1 2

    M аналогично получить
    1 3

    M и тд Процесс заканчивается матрицей
    1

    n
    M
     тк
    1 1


    M
    M
    n
    . Обращение можно начать и с правого нижнего угла матрицы
    M .
    Метод Ершова (метод пополнения)
    На основе исходной матрицы A и единичной матрицыE строится последовательность матриц
    ,
    )
    0
    (
    ,
    )
    (
    ,
    '
    )
    (
    .....,
    ,
    )
    1
    (
    ,
    '
    )
    1
    (
    ,
    )
    0
    (
    E
    A
    A
    где
    n
    A
    n
    A
    A
    A
    A











    ,
    0
    ,
    1
    ,
    )
    1
    (
    '
    )
    (
    m
    ij
    a
    m
    ij
    a
    если
    если
    если
    m
    i
    m
    i
    m
    i


     ,
    и
    и
    ;
    ,
    j
    i
    j
    i













    )
    1
    (
    1
    /
    )
    1
    (
    *
    '
    )
    (
    '
    )
    (
    )
    (
    m
    mm
    a
    m
    mj
    a
    m
    im
    a
    m
    ij
    a
    m
    ij
    a
    ;
    n
    m
    j
    i
    ...,
    ,
    2
    ,
    1
    ,
    ,

    Матрица
    )
    1
    (
    )
    (

    A
    A
    n
    Матрицы '
    )
    (
    '
    )
    2
    (
    '
    )
    1
    (
    ........,
    ,
    ,
    n
    A
    A
    A
    являются вспомогательными
    Метод Фаддеева
    Напомним что следом (spur) матрицы A называется сумма ее элементов на главной диагонали:


    i
    ii
    a
    SpA

    n
    i
    ...,
    ,
    2
    ,
    1


    Вычисление обратной матрицы
    1

    A
    порядка
    n производится по следующим формулам:
    1
    ,
    1
    ,
    ;
    ,
    1 1
    ,
    ;
    ,
    2 1
    ,
    ;
    ,
    ,
    1 1
    1 1
    1 1
    1 1
    2 1
    2 2
    2 2
    2 1
    2 1
    1 1
    1 1
    1


























    n
    n
    n
    n
    n
    n
    n
    n
    n
    n
    n
    n
    n
    B
    p
    A
    SpA
    n
    p
    AB
    A
    E
    p
    A
    B
    SpA
    n
    p
    AB
    A
    E
    p
    A
    B
    SpA
    p
    AB
    A
    E
    p
    A
    B
    SpA
    p
    A
    A

    41
    20.
    Прямые методы решения СЛАУ. Алгоритм метода Гаусса с
    частичным выбором ведущего коэффициента по столбцу. Ошибки и
    затраты машинного времени.
    Метод Гаусса
    Методом Гаусса называют точный метод решения невырожденной системы линейных уравнений состоящий в том что последовательным исключением неизвестных систему
    i
    n
    j
    j
    ij
    b
    x
    a


    1

    n
    i
    ...,
    ,
    2
    ,
    1

     приводят к эквивалентной системе с верхней треугольной матрицей
    ,
    ,
    ,
    ,
    2 2
    2 1
    1 2
    12 1
    n
    n
    n
    n
    n
    n
    d
    x
    d
    x
    c
    x
    d
    x
    c
    x
    c
    x








    решение которой находят по рекуррентным формулам





    n
    i
    k
    k
    ik
    i
    i
    x
    c
    d
    x
    1

    n
    n
    d
    x

    1
    ....,
    ,
    2
    ,
    1



    n
    n
    i

    Существует много вариантов этого метода Рассмотрим схему единственного деления Она эффективна когда максимальные по модулю коэффициенты уравнений находятся на главной диагонали матрицы Это положительно определенные матрицы и матрицы обладающие свойством диагонального преобладания:
    n
    i
    a
    a
    n
    i
    j
    j
    ii
    ij
    ...,
    ,
    2
    ,
    1
    ,|
    |
    |
    |
    ,
    1






    Пусть исходная система имеет вид
    ....,
    ,
    1 1
    1 1
    1 11
    n
    n
    nn
    n
    n
    n
    b
    x
    a
    x
    a
    b
    x
    a
    x
    a






    (1)
    Предположим что
    0 11

    a
     и разделим обе части первого уравнения системы на
    11
    a  В результате получим

    42
    )
    1
    (
    1
    )
    1
    (
    1 2
    )
    1
    (
    12 1
    b
    x
    a
    x
    a
    x
    n
    n




     (2) где
    11 1
    )
    1
    (
    1
    / a
    a
    a
    j
    j


    n
    j
    ,....,
    3
    ,
    2


    11 1
    )
    1
    (
    1
    / a
    b
    b

     С помощью уравнения (2) исключим во всех уравнениях системы (1) начиная со второго слагаемые содержащие
    1
    x
     Для этого умножаем обе части уравнения (2) последовательно на
    1 31 21
    ...,
    ,
    ,
    n
    a
    a
    a
    и вычитаем соответственно из второго третьего  n -го уравнения системы (1) В результате получаем систему порядок которой на единицу меньше порядка исходной системы:
    ,
    .....,
    ,
    )
    1
    (
    )
    1
    (
    2
    )
    1
    (
    2
    )
    1
    (
    2
    )
    1
    (
    2 2
    )
    1
    (
    22
    n
    n
    nn
    n
    n
    n
    b
    x
    a
    x
    a
    b
    x
    a
    x
    a






    где
    )
    1
    (
    1 1
    )
    1
    (
    j
    i
    ij
    ij
    a
    a
    a
    a



    n
    j
    i
    .....,
    ,
    3
    ,
    2
    , 

    )
    1
    (
    1 1
    )
    1
    (
    b
    a
    b
    b
    i
    i
    i



    n
    i
    ...,
    ,
    3
    ,
    2


    Аналогично преобразуем полученную систему В результате n - кратного повторения этого преобразования получим систему с треугольной матрицей:
    ,
    2 2
    3 23 2
    1 1
    3 13 2
    12 1
    ...,
    ,
    ,
    n
    n
    n
    n
    n
    n
    d
    x
    d
    x
    c
    x
    c
    x
    d
    x
    c
    x
    c
    x
    c
    x










    (3) которая эквивалентна системе (1) и легко решается Найденное из последнего уравнения
    n
    x
    подставляют в предпоследнее уравнение и находят
    1

    n
    x
     затем
    2

    n
    x
     и тд до
    1
    x
     которое находят из первого уравнения системы когда уже известны
    2 2
    1
    ...,
    ,
    ,
    ,
    x
    x
    x
    x
    n
    n
    n



    Таким образом метод Гаусса содержит прямой ход на котором исходную систему преобразуют к треугольному виду и обратный ход на котором решают треугольную систему (3) эквивалентную исходной
    На рис.4.1 и 4.2 представлены алгоритмы прямого хода и обратного хода при решении системы.

    43
    Рис.4.1 – прямой ход алгоритма решения системы линейных алгебраических уравнений методом Гаусса по схеме с частичным выбором ведущего коэффициента по столбцу
    начало
    n
    j
    n
    i
    a
    n
    ij
    )
    1
    (
    0
    ),
    1
    )(
    1
    (
    0
    ,
    ,








    уравнений
    ских
    алгебраиче
    линейных
    системы
    частей
    правых
    и
    тов
    коэффициен
    матрицы
    ввод
    )
    2
    )(
    1
    (
    0


    n
    i
    i
    m
    )
    1
    )(
    1
    )(
    1
    (



    n
    i
    k
    mi
    ki
    a
    a

    k
    m
    нет
    k
    n
    i
    j
    )
    1
    (

    z
    a
    a
    a
    a
    z
    mj
    mj
    ij
    ij



    ,
    ,
    j
    ii
    a
    c
    n
    i
    j
    )
    1
    (

    c
    a
    a
    ij
    ij
    /

    j
    )
    1
    )(
    1
    )(
    1
    (



    n
    i
    k
    ki
    a
    b
    n
    i
    l
    )
    1
    (

    il
    kl
    kl
    a
    b
    a
    a
    *


    i
    k
    l
    ,
    ,
    1 1
    2




















    )
    1
    (
    строки
    ю
    n
    по
    той
    i
    с
    столбца
    го
    i
    части
    в
    фициента
    коэф
    модулю
    по
    мального
    макси
    поиск












    местами
    меняются
    строка
    я
    i
    и
    м
    эффициенто
    ко
    модулю
    по
    макс
    с
    строка

    44
    Другие прямые методы: Жордана-Гаусса, ортогональных строк, с ленточными коэффициентами, метод Холецкого, метод квадратного корня, LUразложения, метод прогонки, метод вращения.
    21.
    Итерационные методы решения СЛАУ. Алгоритм метода Гаусса-
    Зейделя.
    Для систем средней размерности чаще используют прямые методы
    Итерационные методы применяют для решения задач большой размерности когда использование прямых затруднено из-за необходимости выполнения чрезмерно большого числа арифметических операций Большие системы уравнений как правило
    Рис.4.2 – обратный ход алгоритма решения системы линейных алгебраических уравнений методом Гаусса по схеме с частичным
    2 1
    ,
    1
    ,
    1 1
    /





    n
    n
    n
    n
    n
    a
    a
    x
    0
    )
    1
    )(
    2
    (


    n
    k
    0

    s
    )
    1
    )(
    1
    )(
    1
    (



    n
    k
    j
    j
    kj
    x
    a
    s
    *


    j
    s
    a
    x
    kn
    k


    k
    )
    1
    )(
    1
    (
    0
    ,


    n
    i
    x
    i





    системы
    решения
    вывод
    конец

    45 бывают разреженными Методы исключения приводят к тому что большое число нулевых элементов превращаются в ненулевые и матрица теряет свойство разреженности А в ходе итерационного процесса матрица не меняется и остается разреженной Большая эффективность итерационных методов по сравнению с прямыми методами связана с возможностью существенного использования разреженных матриц.
    Методы: простой итерации(Якоби), метод релаксации
    Метод Зейделя (метод Гаусса-Зейделя

    процесс Либмана

    метод
    последовательных замещений)
    На k+1-й итерации компоненты приближения
    )
    1
    ( 
    k
    x
    вычисляются по формулам:
    ,
    ,
    ,
    1
    (
    1 1
    ,
    )
    1
    (
    3 3
    )
    1
    (
    2 2
    )
    1
    (
    1 1
    )
    1
    (
    3
    )
    (
    3
    )
    (
    1 1
    ,
    3
    )
    1
    (
    2 32
    )
    1
    (
    1 31
    )
    1
    (
    3 2
    )
    (
    2
    )
    (
    1 1
    ,
    2
    )
    (
    3 23
    )
    1
    (
    1 21
    )
    1
    (
    2 1
    )
    (
    1
    )
    (
    1 1
    ,
    1
    )
    (
    3 13
    )
    (
    2 12
    )
    1
    (
    1
    n
    k
    n
    n
    n
    k
    n
    k
    n
    k
    n
    k
    n
    k
    n
    n
    k
    n
    n
    k
    k
    k
    k
    n
    n
    k
    n
    n
    k
    k
    k
    k
    n
    n
    k
    n
    n
    k
    k
    k
    c
    x
    b
    x
    b
    x
    b
    x
    b
    x
    c
    x
    b
    x
    b
    x
    b
    x
    b
    x
    c
    x
    b
    x
    b
    x
    b
    x
    b
    x
    c
    x
    b
    x
    b
    x
    b
    x
    b
    x











































    Метод Якоби ориентирован на системы с матрицами близкими к диагональным а метод Зейделя – на системы с матрицами близкими к нижним треугольным
    Алгоритм метода Зейделя представлен на рис.4.3.

    46
    Рис.4.3 – алгоритм итерационного метода Гаусса-Зейделя решения систем линейных алгебраических уравнений
    начало
    n
    j
    n
    i
    a
    n
    ij
    )
    1
    (
    0
    ),
    1
    )(
    1
    (
    0
    ,
    ,



    )
    1
    )(
    1
    (
    0
    ,
    ,


    n
    i
    x
    i

    )
    1
    )(
    1
    (
    0


    n
    i
    0

    s
    )
    1
    )(
    1
    (
    0


    n
    j
    j
    ij
    x
    a
    s
    *


    j
    z
    x
    z
    x
    z
    t
    x
    a
    s
    a
    z
    i
    i
    i
    i
    ii
    in






    ,
    /
    )
    (
    ,
    /
    )
    (
    i
    )
    1
    )(
    1
    (
    0


    n
    i


    i
    t
    да
    i
    )
    1
    )(
    1
    (
    0
    ,


    n
    i
    x
    i
    конец








    уравнений
    браических
    алге
    линейных
    системы
    частей
    правых
    и
    ентов
    коэффици
    матрицы
    ввод





    системы
    решения
    ого
    приближенн
    и
    ошибки
    ввод


     
    ошибок
    текущих
    массив
    t

    системы
    решения
    вывод

    47
    22.
    Сравнение прямых и итерационных методов решения СЛАУ.
    Рекомендации при вычислении матричных выражений.
    Итерационные методы применяют для решения задач большой размерности когда использование прямых затруднено из-за необходимости выполнения чрезмерно большого числа арифметических операций Большие системы уравнений как правило бывают разреженными Методы исключения приводят к тому что большое число нулевых элементов превращаются в ненулевые и матрица теряет свойство разреженности А в ходе итерационного процесса матрица не меняется и остается разреженной Большая эффективность итерационных методов по сравнению с прямыми методами связана с возможностью существенного использования разреженных матриц
    В матричных выражениях следует избегать вычисления обратных матриц, т.к. на это требуется большее время, чем на остальные вычисления.
    Например, требуется вычислить
    W
    WD
    CA
    B
    V
    1 1
    1




    при известных
    W
    D
    C
    B
    A
    ,
    ,
    ,
    ,
    Ошибочно вычислять сначала
    1 1
    1
    ,
    ,



    D
    A
    B
    , а затем – по формуле.
    Нужно вычислять с меньшими затратами машинного времени, в следующей последовательности.
    Решая систему
    W
    Dx
    , находят
    W
    D
    x
    1


    , затем -
    Wx
    y
    Решая систему
    y
    Az
    , находят
    y
    A
    z
    1


    , затем -
    Cz
    u
    Решая систему
    u
    BV
    , находят
    u
    B
    V
    1


    23.
    Постановка задачи аппроксимации (регрессии). Выбор критерия.
    1   2   3   4   5


    написать администратору сайта