Кіріспе
Математикалық ұғым
Сызықтық алгебрада Вандермонд матрицасы — Александр Теофил Вандермондтың есімімен аталған, әрбір қатарында геометриялық прогрессия мүшелері бар матрица: барлық нөлдік индекс үшін мүшелері бар матрица, саның j-інші дәрежесі, және кейбір авторлар Вандермонд матрицасын жоғарыда көрсетілген матрицаның транспозіциясы деп анықтайды. Яғни, коэффициенттерден полиномдардың мәндеріне бейнелеу V матрицасы бар биективті сызықтық бейнелеу болып табылады, ал интерполяция мәселесінің бірегей шешімі бар. Бұл нәтиже біртектілік теоремасы деп аталады және ол полиномдар үшін қытайлық қалдық теоремасының ерекше жағдайы болып табылады. Статистикада теңдеуі Вандермонд матрицасы полиномдық регрессияның жобалау матрицасы екенін білдіреді. Сандық талдауда теңдеуін Гаусс жою арқылы шешу O(n³) уақыт күрделілігі бар алгоритмге әкеледі. Вандермонд матрицасының құрылымын пайдаланып, Ньютонның бөлінген айырмашылықтар әдісін (немесе Лагранж интерполяция формуласын) O(n²) уақытында теңдеуді шешу үшін қолдануға болады, бұл сонымен қатар UL-факторизацияны да береді. Нәтижесінде алынған алгоритм өте дәл шешімдер береді, тіпті егер жағдайы нашар болса да. Егер мәндер шекті өрісқа жатса, онда Вандермонд детерминанты Мур детерминанты деп аталады және ол BCH кодтары мен Рид-Соломон қателіктерді түзету кодтарының теориясында маңызды қасиеттерге ие. Дискретті Фурье түрлендірімі белгілі бір Вандермонд матрицасы, DFT матрицасы арқылы анықталады, онда n-інші бірліктің түбірлері ретінде таңдалады. Жылдам Фурье түрлендірімі осы матрицаның вектормен көбейтіндісін O(n log₂n) уақытында есептейді. Кванттық Холл эффектісінің физикалық теориясында Вандермонд детерминанты 1-ге тең толтыру коэффициенті бар Лафлин толқындық функциясы Слейтер детерминантына тең екенін көрсетеді. Бұл фракциялық кванттық Холл эффектінде 1-ден өзгеше толтыру коэффициенттері үшін енді дұрыс емес. Полиэдрлердің геометриясында Вандермонд матрицасы циклдық политоптардың кез келген бетінің қалыптандырылған көлемін береді. Атап айтқанда, егер циклдық политоптың бетіне сәйкес келсе, онда.
In linear algebra, a Vandermonde matrix, named after Alexandre Théophile Vandermonde, is a matrix with the terms of a geometric progression in each row: an matrix
with entries , the jth power of the number , for all zero based indices and Some authors define the Vandermonde matrix as the transpose of the above matrix. That is, the map from coefficients to values of polynomials is a bijective linear mapping with matrix V, and the interpolation problem has a unique solution. This result is called the unisolvence theorem, and is a special case of the Chinese remainder theorem for polynomials. In statistics, the equation means that the Vandermonde matrix is the design matrix of polynomial regression. In numerical analysis, solving the equation naïvely by Gaussian elimination results in an algorithm with time complexity O(n3). Exploiting the structure of the Vandermonde matrix, one can use Newton's divided differences method (or the Lagrange interpolation formula) to solve the equation in O(n2) time, which also gives the UL factorization of The resulting algorithm produces extremely accurate solutions, even if is ill conditioned. When the values belong to a finite field, the Vandermonde determinant is also called the Moore determinant, and has properties which are important in the theory of BCH codes and Reed–Solomon error correction codes. The discrete Fourier transform is defined by a specific Vandermonde matrix, the DFT matrix, where the are chosen to be nth roots of unity. The Fast Fourier transform computes the product of this matrix with a vector in O(n log2n) time. In the physical theory of the quantum Hall effect, the Vandermonde determinant shows that the Laughlin wavefunction with filling factor 1 is equal to a Slater determinant. This is no longer true for filling factors different from 1 in the fractional quantum Hall effect. In the geometry of polyhedra, the Vandermonde matrix gives the normalized volume of arbitrary faces of cyclic polytopes. Specifically, if is a face of the cyclic polytope corresponding to , then
Анықтамалық фактор
Квадрат Вандермонд матрицасының детерминанты Вандермонд полиномдары немесе Вандермонд детерминанты деп аталады. Оның мәні – нөлден өзгеше, егер және тек қана барлық шамалар өзгеше болса, ондағы полином. Вандермонд детерминанты бұрын дискриминант деп аталған, бірақ қазіргі терминологияда көпмүшеліктердің дискриминанты – түбірлерінің Вандермонд детерминантының квадраты. Вандермонд детерминанты – бұл , екі шаманы алмастыру белгісін өзгертетін, сондықтан шамалардың ретіне байланысты. Керісінше, дискриминант ешқандай ретке тәуелді емес, сондықтан Галуа теориясы дискриминанттың көпмүшелік коэффициенттерінің функциясы екенін көрсетеді. Детерминант формуласы төменде үш түрлі жолмен дәлелденген. Біріншісі, көпмүшелік қасиеттерді, әсіресе көпөлшемді көпмүшеліктердің бірегей факторлау қасиеттерін пайдаланады. Тұжырымдамалық тұрғыдан қарапайым болғанымен, ол абстрактілі алгебраның элементарлық емес ұғымдарын қамтиды. Екінші дәлел векторлық кеңістікте негізді өзгерту және сызықтық түрлендірудің детерминанты туралы сызықтық алгебра ұғымдарына негізделген. Осы процесте Вандермонд матрицасының LU жіктелуі есептеледі. Үшінші дәлелдеме элементарлырақ, бірақ күрделірек, тек элементарлық қатар және баған операцияларын қолданады.
which is non zero if and only if all are distinct. The Vandermonde determinant was formerly sometimes called the discriminant, but in current terminology the discriminant of a polynomial is the square of the Vandermonde determinant of the roots The Vandermonde determinant is an alternating form in the , meaning that exchanging two changes the sign, and thus depends on order for the By contrast, the discriminant does not depend on any order, so that Galois theory implies that the discriminant is a polynomial function of the coefficients of
The determinant formula is proved below in three ways. The first uses polynomial properties, especially the unique factorization property of multivariate polynomials. Although conceptually simple, it involves non elementary concepts of abstract algebra. The second proof is based on the linear algebra concepts of change of basis in a vector space and the determinant of a linear map. In the process, it computes the LU decomposition of the Vandermonde matrix. The third proof is more elementary but more complicated, using only elementary row and column operations.
Вандермонд матрицасының рангі
m × n тікбұрышты Вандермонд матрицасы, егер m ≤ n болса, дәрежесі m-ге тең болуы үшін барлық xi-тер ерекше болуы керек және керісінше. Егер m ≥ n болса, m × n тікбұрышты Вандермонд матрицасының дәрежесі n-ге тең болуы үшін xi-тердің n-і ерекше болуы керек. Квадраттық Вандермонд матрицасы xi-тер ерекше болған жағдайда ғана кері айналады. Оның кері матрицасын табу формуласы белгілі (төменде қараңыз).
Кері Vandermonde матрицасы
Жоғарыда «Қолданылуларында» түсіндірілгендей, жақындастыру шартын қанағаттандыру үшін полиномдық интерполяция мәселесі матрицалық теңдеуге баламалы, оның бірегей шешімі бар. Интерполяция мәселесін шешетін басқа да белгілі формулалар бар, олар осы бірегей шешімге баламалы болуы керек, сондықтан олар кері матрицаның нақты формулаларын беруі тиіс. Атап айтқанда, Лагранж интерполяциясы кері матрицаның бағандары Лагранж полиномдарының коэффициенттері екенін көрсетеді. Бұл оңай көрсетіледі: полиномдар үшін анық қанағаттандырады, ал , сондықтан біз көбейтіндіні есептеуге болады, бұл бірлік матрица.
are the coefficients of the Lagrange polynomials where This is easily demonstrated: the polynomials clearly satisfy for while , so we may compute the product , the identity matrix.
Конфузиялық Вандермонд матрицалары
Бұрын айтылғандай, Вандермонд матрицасы сызықтық алгебраның интерполяциялық мәселесін сипаттайды, онда әртүрлі нүктелердегі , мәндеріне негізделген белгілі дәрежелі полиномиалдың коэффициенттерін табуға болады. Егер бұл нүктелер әртүрлі болмаса, онда бұл мәселенің бірегей шешімі жоқ (және сәйкес Вандермонд матрицасы сингуляр болады). Алайда, егер қайталанатын нүктелерде туындылардың мәндерін көрсетсек, онда мәселенің бірегей шешімі болуы мүмкін. Мысалы, мына мәселе барлық үшін бірегей шешімге ие: . Жалпы алғанда, (әрқашан да емес) сандар деп есептейік, және қарапайымдық үшін тең мәндер іргелес деп есептейік: мұндағы және әртүрлі. Онда тиісті интерполяциялық мәселе келесідей болады:
where , has a unique solution for all with In general, suppose that are (not necessarily distinct) numbers, and suppose for simplicity that equal values are adjacent:
where and are distinct. Then the corresponding interpolation problem is
The corresponding matrix for this problem is called a confluent Vandermonde matrix, given as follows. If , then for a unique (denoting ). We let
This generalization of the Vandermonde matrix makes it non singular, so that there exists a unique solution to the system of equations, and it possesses most of the other properties of the Vandermonde matrix. Its rows are derivatives (of some order) of the original Vandermonde rows. Another way to derive this formula is by taking a limit of the Vandermonde matrix as the 's approach each other. For example, to get the case of , take subtract the first row from second in the original Vandermonde matrix, and let : this yields the corresponding row in the confluent Vandermonde matrix. This derives the generalized interpolation problem with given values and derivatives as a limit of the original case with distinct points: giving is similar to giving for small Geometers have studied the problem of tracking confluent points along their tangent lines, known as compacitification of configuration space.
Осы мәселе үшін сәйкес келетін матрица конfluentтік Вандермонд матрицасы деп аталады, ол келесідей беріледі. Егер тек бір дауыс болса (оның белгіленуі мен орны көрсетілсін). Біз Вандермонд матрицасын жалпылап, оны сингуляр емес етеміз, сондықтан теңдеулер жүйесінің бірегей шешімі бар және ол Вандермонд матрицасының көптеген басқа қасиеттерін сақтайды. Оның қатарлары түпнұсқа Вандермонд қатарларының туындылары (кейбір ретпен). Бұл формуланың тағы бір жолы – Вандермонд матрицасының шегін алу, егер нүктелер бір-біріне жақындаса. Мысалы, жағдайын алу үшін бастапқы Вандермонд матрицасының екінші қатарынан бірінші қатарын алып тастаңыз, және мынаны алыңыз: бұл конfluentтік Вандермонд матрицасындағы сәйкес қатарды береді. Осылайша, берілген мәндер мен туындылар бойынша жалпыланған интерполяциялық мәселе, ерекше нүктелер бар бастапқы жағдайдың шегі ретінде алынады: кішкентай мәндерді беру, үлкен мәндерді беруге ұқсас. Геометрлер конfluentтік нүктелерді олардың жанама сызықтары бойынша қадағалау мәселесін зерттеді, бұл конфигурациялық кеңістікті тығыздау деп аталады.
where , has a unique solution for all with In general, suppose that are (not necessarily distinct) numbers, and suppose for simplicity that equal values are adjacent:
where and are distinct. Then the corresponding interpolation problem is
The corresponding matrix for this problem is called a confluent Vandermonde matrix, given as follows. If , then for a unique (denoting ). We let
This generalization of the Vandermonde matrix makes it non singular, so that there exists a unique solution to the system of equations, and it possesses most of the other properties of the Vandermonde matrix. Its rows are derivatives (of some order) of the original Vandermonde rows. Another way to derive this formula is by taking a limit of the Vandermonde matrix as the 's approach each other. For example, to get the case of , take subtract the first row from second in the original Vandermonde matrix, and let : this yields the corresponding row in the confluent Vandermonde matrix. This derives the generalized interpolation problem with given values and derivatives as a limit of the original case with distinct points: giving is similar to giving for small Geometers have studied the problem of tracking confluent points along their tangent lines, known as compacitification of configuration space.