Матрица Вандермонда
Введение
Александр Теофил Вандермонд (28 февраля 1735 - 1 января 1796) - французский музыкант и математик, известный благодаря своей работе в области высшей алгебры.
Главным увлечением Вандермонда длительное время была лишь музыка, но к 35-ти годам юный ученый обратился к математике. Первым делом он провел исследование симметрических функций и решения круговых полиномов, после чего выпустил три статьи: про задачу о ходе коня, про комбинаторику и про основы теории детерминантов.
В честь Александра Теофила был назван специальный класс матриц - матрицы Вандермонда, о котором пойдет речь в данной статье. [1]
Матрица Вандермонда
В линейной алгебре матрица Вандермонда, представляет собой матрицу с членами геометрической прогрессии в каждой строке.
Давайте рассмотрим узлы
Тогда первый столбец матрицы будет полностью заполнен
Применение - интерполяция
Задача интерполяции заключается в том, чтобы найти полином вида:
который удовлетворяет условию:
Сделать это можно используя матрицу Вандермонда, следуя формуле:
где
Пример
Даны три точки:
Для начала, построим матрицу Вандермонда.
Далее, расширим матрицу значениями вектора
Пользуясь правилами сложения и вычитания строк матрицы, упростим её до формы:
Далее, решаем систему методом подстановки,
Таким образом, наш полином равен
Код
Мы создадим собственную функцию vandermonde_matrix,которая вычисляет матрицу
Вандермонда
Входные данные функции — степень
import numpy as np
def vandermonde_matrix(n):
A=np.zeros((n+1,n+1))
for i in range (n+1):
for j in range (n+1):
A[i][j]=(i/n)**j if n !=0 else 1
return A
print(vandermonde_matrix(3)) #примерЧисло обусловленности
В численном анализе число обусловленности функции показывает насколько может измениться значение функции при небольшом изменении аргумента. Число обусловленности отражает, насколько чувствительна функция к изменениям или ошибкам на входе и насколько ошибка на выходе является результатом ошибки на входе. [3]
Число обусловленности для матрицы Вандермонда будет рассчитываться как произведение двух норм - нормы матрицы Вандермонда и нормы обратной матрицы Вандермонда.
Код
Для
вычислим число обусловленности матрицы и построим график зависимости числа обусловленности матрицы Вандермонда от
import numpy as np
import matplotlib.pyplot as plt
def vandermonde_matrix(n):
A=np.zeros((n+1,n+1))
for i in range (n+1):
for j in range (n+1):
A[i][j]=(i/n)**j if n !=0 else 1
return A
cond_vandermonde=np.zeros(101)
for i in range (1, 101):
matrix=vandermonde_matrix(i)
matrix_inv=np.linalg.inv(matrix)
cond_vandermonde[i]=np.array(np.linalg.norm(matrix)*np.linalg.norm(matrix_inv))
n_values=np.zeros(101)
for i in range(1, 101):
n_values[i]=np.array(i)
plt.semilogy(n_values, cond_vandermonde)
plt.ylabel('n')
plt.xlabel('Число Обусловленности')
plt.title('Зависимость числа обусловленности от n')
plt.show()Мы можем заметить, что когда увеличивается размер матрицы, число обусловленности также возрастает. Это связано с тем, что матрица Вандермонда содержит всё большие и большие разности элементов, что приводит к увеличению значений определителя.
Из-за того, что определитель матрицы Вандермонда может сильно возрастать с увеличением размера матрицы, происходят численные нестабильности и потери точности вычислений. Благодаря чему мы можем подвести итог.
Заключение
Метод интерполяции с использованием матрицы Вандермонда эффективен для небольшого количества точек, когда нужно построить матрицу небольшого размера. Однако, для больших данных или случаев с высокой чувствительностью к точности, могут потребоваться более устойчивые методы.