Division synthétique et factorisation de matrices

Samuel Barabé et François Dubeau

Département de mathématiques Université de Sherbrooke Sherbrooke (Qc), Canada, J1K 2R1

samuel.barabe@usherbrooke.ca francois.dubeau@usherbrooke.ca

Résumé : La division synthétique et les matrices de changement de bases associées sont utilisées pour obtenir la factorisation de la matrice inverse soit d’une matrice bi-diagonale ou soit d’une matrice bi-diagonale par blocs.

Mots clefs : division synthétique, changement de bases, matrice bidiagonale, inversion, factorisation.

1. Introduction

L’algorithme de division synthétique est un procédé de division d’un polynôme de degré n par un polynôme de degré 1 [3]. Il est aussi appelé méthode de Horner et sert à évaluer un polynôme en un point par multiplication emboîtée [1, 2, 3]. En appliquant la division synthétique on fait essentiellement un changement de base. Nous allons élaborer les liens qui existent entre cet algorithme et les matrices de changement de base. Nous allons alors utiliser ce procédé pour obtenir une factorisation de l’inverse d’une matrice bi-diagonale. Par la suite, nous allons utiliser la division synthétique avec des polynômes de degré 2 [1], ce qui nous conduira à des matrices bi-diagonales par bloc particulières pour lesquelles ont obtiendra l’inverse et une factorisation de l’inverse.

2. La Division Synthétique

Soit p(x) un polynôme de degré n représenté sous la forme de Newton avec centres c_{1}, c_{2}, ..., c_{n}

p(x) = a_{0} + a_{1}(x − c_{n}) + a_{2}(x − c_{n−1)}(x − c_{n}) + ... + a_{n} ∏_{j=1}^{n}(x − c_{j})

= ∑_{i=0}^{n} a_{i} ∏_{j=n−i+1}^{n}(x − c_{j})

où

∏_{j=n+1}^{n}(x − c_{j}) = 1.

Sous cette forme p(x) est représenté par rapport à la base

B = {1, (x − c_{n}), (x − c_{n−1})(x − c_{n}), ..., ∏_{j=1}^{n}(x − c_{j})}

de ℙ^{n}. En effectuant la division de p(x) par x − c_{n+1}, on obtient la représentation de p(x) par rapport à la base

B′ = {1, (x − c_{n+1}), (x − c_{n})(x − c_{n+1}), ..., ∏_{j=2}^{n+1}(x − c_{j})}.

Ainsi c_{i+1} remplace c_{i} pour i = n, n − 1, ...1. En effet nous avons successivement

p(x) = ∑_{i=0}^{n} a_{i} ∏_{j=n−i+1}^{n}(x − c_{j})

= a_{n} ∏_{j=1}^{n}(x − c_{j}) + ∑_{i=0}^{n−1} a_{i} ∏_{j=n−i+1}^{n}(x − c_{j})

= a_{n} ∏_{j=2}^{n+1}(x − c_{j}) + a_{n}(c_{n+1} − c_{1}) ∏_{j=2}^{n}(x − c_{j}) + ∑_{i=0}^{n−1} a_{i} ∏_{j=n−i+1}^{n}(x − c_{j})

= an^{′} ∏_{j=2}^{n+1}(x − c_{j}) + [a_{n}(c_{n+1} − c_{1}) + a_{n−1}] ∏_{j=2}^{n}(x − c_{j}) + ∑_{i=0}^{n−2} a_{i} ∏_{j=n−i+1}^{n}(x − c_{j})

= ∑_{l=0}^{1} an−l^{′} ∏_{j=2+l}^{n+1}(x − c_{j}) + [an−1^{′}(c_{n+1} − c_{2}) + a_{n−2}] ∏_{j=3}^{n}(x − c_{j}) + ∑_{i=0}^{n−3} a_{i} ∏_{j=n−i+1}^{n}(x − c_{j})

⋮
= ∑_{l=0}^{k−1} an−l^{′} ∏_{j=2+l}^{n+1}(x − c_{j}) + [an−(k−1)^{′}(c_{n+1} − c_{k}) + a_{n−k}] ∏_{j=k+1}^{n}(x − c_{j}) + ∑_{i=0}^{n−(k+1)} a_{i} ∏_{j=n−i+1}^{n}(x − c_{j})

⋮
= ∑_{l=0}^{n−2} an−l^{′} ∏_{j=2+l}^{n+1}(x − c_{j}) + [a2^{′}(c_{n+1} − c_{n−1}) + a_{1}](x − c_{n}) + a_{0}

= ∑_{l=0}^{n−1} an−l^{′} ∏_{j=2+l}^{n+1}(x − c_{j}) + [a1^{′}(c_{n+1} − c_{n}) + a_{0}]

= ∑_{l=0}^{n} an−l^{′} ∏_{j=2+l}^{n+1}(x − c_{j})

où nous avons posé successivement an^{′} = a_{n} et an−k^{′} = an−(k−1)^{′}(c_{n+1} − c_{k}) + a_{n−k} pour k = 1, ..., n.

En réécrivant ces égalitées sous forme matricielle, on pose

[p]_{B} = [a_{0} ; a_{1} ; ⋮ ; a_{n}]  et  [p]_{B′} = [a0^{′} ; a1^{′} ; ⋮ ; an^{′}] ,

alors

P_{B,B′} = [\begin{matrix}1 & c_{n} − c_{n+1} & 0 & ⋯ & 0 \\ 0 & 1 & c_{n−1} − c_{n+1} & ⋯ & 0 \\ 0 & 0 & 1 & ... & ⋮ \\ ⋮ & ⋮ & & ... & c_{1} − c_{n+1} \\ 0 & 0 & ⋯ & & 1 \end{matrix}]

et on obtient

[p]_{B} = P_{B,B′} [p]_{B′} .

3. Division Synthétique et facteurs de degré 1

3.1. Bases et matrices de changement de base. Soit une suite de réels c_{0}, c_{1}, c_{2}, ... et considérons les bases de ℙ^{n} données par

B_{k} = \{e_{j}^{k}(x) | \begin{matrix}e_{j}^{k}(x) = 1 & pour j = 0, \\ e_{j}^{k}(x) = ∏_{i=k+n−j}^{k+n−1}(x − c_{i}) & pour j = 1, 2, ..., n \end{matrix} \}

pour k = 0, 1, 2, ...

La division synthétique consiste alors à passer de la représentation d’un polynôme par rapport à la base B_{k} à la représentation par rapport à la base B_{k+1}. Avant d’indiquer les liens entre ces représentations, donnons quelques propriétés élémentaires des éléments des bases B_{k}.

Théorème 3.1. Les éléments {e_{j}^{k}(x)}_{j=0}^{n} des bases B_{k} vérifient

degré e_{j}^{k}(x) = j

pour j = 0, 1, ..., n, et

e_{j}^{k}(x) = (x − c_{n+k−j})e_{j−1}^{k}(x),
e_{j}^{k+1}(x) = (x − c_{k+n})e_{j−1}^{k}(x),
e_{j}^{k+1}(x) = e_{j}^{k}(x) + (c_{k+n−j} − c_{k+n})e_{j−1}^{k}(x)

pour j = 1, 2, ..., n.

Démonstration. Comme e_{0}^{k}(x) = 1, le degré de e_{0}^{k}(x) est 0. Pour j = 1, 2, ..., n on a

e_{j}^{k}(x) = ∏_{i=k+n−j}^{k+n−1}(x − c_{i}) = x^{j} + (polynôme de degré ≤ j − 1)

d’où le résultat. Pour les trois autres relations on a

e_{j}^{k}(x) = ∏_{i=k+n−j}^{k+n−1}(x − c_{i}) = (x − c_{k+n−j}) ∏_{i=k+n−(j−1)}^{k+n−1}(x − c_{i}) = (x − c_{k+n−j})e_{j−1}^{k}(x),

e_{j}^{k+1}(x) = ∏_{i=(k+1)+n−j}^{(k+1)+n−1}(x−c_{i}) = (x−c_{k+n}) ∏_{i=k+n−(j−1)}^{k+n−1}(x−c_{i}) = (x−c_{k+n})e_{j−1}^{k}(x)

et

e_{j}^{k+1}(x) = (x − c_{k+n})e_{j−1}^{k}(x) = [(x − c_{k+n−j}) + (c_{k+n−j} − c_{k+n})]e_{j−1}^{k}(x)
= e_{j}^{k}(x) + (c_{k+n−j} − c_{k+n})e_{j−1}^{k}(x).  □

En posant [e^{k}(x)]^{T} = [e_{0}^{k}(x), e_{1}^{k}(x), ..., e_{n}^{k}(x)]^{T}, nous avons

[e^{k+1}(x)]^{T} = [e^{k}(x)]^{T} P_{k,k+1}

où la matrice de changement de base P_{k,k+1} est donnée par

P_{k,k+1} = [\begin{matrix}1 & c_{k+n−1} − c_{k+n} & 0 & ⋯ & 0 \\ 0 & 1 & c_{k+n−2} − c_{k+n} & & 0 \\ 0 & 0 & 1 & ... & ⋮ \\ ⋮ & ⋮ & & ... & c_{k+n−n} − c_{k+n} \\ 0 & 0 & ⋯ & & 1 \end{matrix}] .

Si la représentation d’un polynôme p(x) de ℙ^{n} par rapport à la base B_{k} est

p(x) = ∑_{j=0}^{n} a_{j}^{k}e_{j}^{k}(x),

en posant [p]_{k}^{T} = [a_{0}^{k}, a_{1}^{k}, ..., a_{n}^{k}]^{T} nous avons

p(x) = [e^{k}(x)]^{T} [p]_{k}.

Ainsi on doit avoir

[e^{k+1}(x)]^{T} [p]_{k+1} = [e^{k}(x)]^{T} P_{k,k+1}[p]_{k+1} = [e^{k}(x)]^{T} [p]_{k},

d’où

[p]_{k} = P_{k,k+1}[p]_{k+1}.

Si on applique m fois la division synthétique à partir de la base B_{k} on passe à la base B_{k+m} et on a

[p]_{k} = [ ∏_{l=k}^{k+m−1} P_{l,l+1}][p]_{k+m}.

Supposons maintenant que pour un certain m ≥ 1 on a c_{k+m+j} = c_{k+j} pour j = 0, 1, ..., n − 1. Alors B_{k} = B_{k+m} et comme [p]_{k} = [p]_{k+m} on en déduit

(3.1)  I = ∏_{l=k}^{k+m−1} P_{l,l+1}.

3.2. Matrices bi-diagonales, inversion et factorisation. On dit qu’une matrice Q = (q_{ij}) est m-diagonale supérieure si elle est triangulaire supérieure et si q_{ij} = 0 lorsque j < i où j > i + m − 1. Lorsque m = 1 elle est diagonale et si m = 2 elle est bi-diagonale. On dira que la matrice m-diagonale est pleine si q_{ij} ≠ 0 lorsque i ≤ j ≤ i + m − 1 pour i = 1, 2, ..., n.

Lemme 3.2. Soient {Q_{k}}_{k=0}^{m−1} m matrices bi-diagonales pleines. Alors

Q = ∏_{k=0}^{m−1} Q_{k}

est une matrice (m+1)-diagonale pleine. Alors, si Q est une (n+1, n+1)-matrice, Q est triangulaire supérieure pleine si m ≥ n.

Démonstration. Il suffit de multiplier les matrices. □

Lemme 3.3. Toute matrice bi-diagonale pleine de la forme

P = [p_{ij}]_{(n+1,n+1)} = [\begin{matrix}1 & α_{12} & 0 & ⋯ & 0 \\ 0 & 1 & α_{23} & & 0 \\ 0 & 0 & 1 & ... & ⋮ \\ ⋮ & ⋮ & & ... & α_{n,n+1} \\ 0 & 0 & ⋯ & & 1 \end{matrix}]

a une inverse triangulaire supérieure pleine de la forme P^{−1} = [γ_{ij}]_{(n+1,n+1)} avec

γ_{ij} = \{ \begin{matrix}0 si i > j, \\ 1 si i = j, \\ (−1)^{(j−i)} ∏_{k=i}^{j−1} α_{k,k+1} si i < j. \end{matrix}

Démonstration. Le calcul de l’inverse est direct. □

Les matrices P_{k,k+1} sont bi-diagonales avec les éléments diagonaux égaux à 1. Nous les utilisons ici pour déterminer l’inverse de matrice bi-diagonale à éléments diagonaux égaux à 1.

Théorème 3.4. Soit une matrice bi-diagonale pleine de la forme

P = [p_{ij}]_{(n+1,n+1)} = [\begin{matrix}1 & α_{12} & 0 & ⋯ & 0 \\ 0 & 1 & α_{23} & & 0 \\ 0 & 0 & 1 & ... & ⋮ \\ ⋮ & ⋮ & & ... & α_{n,n+1} \\ 0 & 0 & ⋯ & & 1 \end{matrix}] .

En posant c_{0}, c_{1}, c_{2}, ..., c_{n} tels que α_{i,i+1} = c_{n−i} −c_{n} pour i = 1, 2, ..., n, et c_{n+l+j} = c_{j} pour j = 0, 1, ..., n − 1 avec l ≥ 1, on a B_{0} = B_{n+l} et alors

P = P_{0,1} et P^{−1} = ∏_{k=1}^{n+l−1} P_{k,k+1}

où la valeur minimale de l est 1.

Démonstration. Par construction, on prend c_{n} arbitraire et on détermine les c_{j} pour j = 0, 1, ..., n − 1 à l’aide des relations données. Le résultat suit de (3.1). □

3.3. Exemple. Soit A une (4, 4)-matrice bi-diagonale

A = [\begin{matrix}1 & 1 & 0 & 0 \\ 0 & 1 & 2 & 0 \\ 0 & 0 & 1 & 3 \\ 0 & 0 & 0 & 1 \end{matrix}]

de telle sorte que n + 1 = 4, α_{12} = 1 et α_{23} = 2 et α_{34} = 3. Ainsi

A^{−1} = ∏_{k=1}^{3} P_{k,k+1} = P_{1,2}P_{2,3}P_{3,4}.

Nous avons

1 = α_{12} = c_{2} − c_{3},
2 = α_{23} = c_{1} − c_{3},
3 = α_{3,4} = c_{0} − c_{3},

et en prenant c_{3} = 0 nous avons c_{0} = 3, c_{1} = 2, c_{2} = 1. Ainsi P_{0,1} = P et

P_{1,2} = [\begin{matrix}1 & c_{3} − c_{4} & 0 & 0 \\ 0 & 1 & c_{2} − c_{4} & 0 \\ 0 & 0 & 1 & c_{1} − c_{4} \\ 0 & 0 & 0 & 1 \end{matrix}] = [\begin{matrix}1 & c_{3} − c_{0} & 0 & 0 \\ 0 & 1 & c_{2} − c_{0} & 0 \\ 0 & 0 & 1 & c_{1} − c_{0} \\ 0 & 0 & 0 & 1 \end{matrix}] = [\begin{matrix}1 & −3 & 0 & 0 \\ 0 & 1 & −2 & 0 \\ 0 & 0 & 1 & −1 \\ 0 & 0 & 0 & 1 \end{matrix}] ,

P_{2,3} = [\begin{matrix}1 & c_{4} − c_{5} & 0 & 0 \\ 0 & 1 & c_{3} − c_{5} & 0 \\ 0 & 0 & 1 & c_{2} − c_{5} \\ 0 & 0 & 0 & 1 \end{matrix}] = [\begin{matrix}1 & c_{0} − c_{1} & 0 & 0 \\ 0 & 1 & c_{3} − c_{1} & 0 \\ 0 & 0 & 1 & c_{2} − c_{1} \\ 0 & 0 & 0 & 1 \end{matrix}] = [\begin{matrix}1 & 1 & 0 & 0 \\ 0 & 1 & −2 & 0 \\ 0 & 0 & 1 & −1 \\ 0 & 0 & 0 & 1 \end{matrix}] ,

et

P_{3,4} = [\begin{matrix}1 & c_{5} − c_{6} & 0 & 0 \\ 0 & 1 & c_{4} − c_{6} & 0 \\ 0 & 0 & 1 & c_{3} − c_{6} \\ 0 & 0 & 0 & 1 \end{matrix}] = [\begin{matrix}1 & c_{1} − c_{2} & 0 & 0 \\ 0 & 1 & c_{0} − c_{2} & 0 \\ 0 & 0 & 1 & c_{3} − c_{2} \\ 0 & 0 & 0 & 1 \end{matrix}] = [\begin{matrix}1 & 1 & 0 & 0 \\ 0 & 1 & 2 & 0 \\ 0 & 0 & 1 & −1 \\ 0 & 0 & 0 & 1 \end{matrix}] .

Donc

A^{−1} = [\begin{matrix}1 & −1 & 2 & −6 \\ 0 & 1 & −2 & 6 \\ 0 & 0 & 1 & −3 \\ 0 & 0 & 0 & 1 \end{matrix}] = [\begin{matrix}1 & −3 & 0 & 0 \\ 0 & 1 & −2 & 0 \\ 0 & 1 & 1 & −1 \\ 0 & 0 & 0 & 1 \end{matrix}] [\begin{matrix}1 & 1 & 0 & 0 \\ 0 & 1 & −2 & 0 \\ 0 & 0 & 1 & −1 \\ 0 & 0 & 0 & 1 \end{matrix}] [\begin{matrix}1 & 1 & 0 & 0 \\ 0 & 1 & 2 & 0 \\ 0 & 0 & 1 & −1 \\ 0 & 0 & 0 & 1 \end{matrix}] . □

4. Division synthétique et facteurs de degré 2

4.1. Bases et matrices de changement de base. Soit une suite de n paires de nombres réels {(α_{i}, β_{i})}_{i=k}^{k+n−1} et considérons les polynômes

e_{j,0}^{k}(x) = \{ \begin{matrix}1 si j = 0 \\ ∏_{i=k+n−j}^{k+n−1}(x^{2} + α_{i}x + β_{i}) si j = 1, 2, ..., n \end{matrix}

et e_{j,1}^{k}(x) = xe_{j,0}^{k}(x) pour j = 0, 1, ..., n où le degré de e_{j,i}^{k}(x) est 2j +i pour i = 0, 1. Nous avons ainsi une base de ℙ^{2n+1}, l’espace des polynômes de degré 2n + 1,

B̃_{k} = {e_{j,0}^{k}(x), e_{j,1}^{k}(x)|j = 0, 1, 2, ..., n}.

Théorème 4.1. Les éléments {e_{j,i}^{k}(x)}_{i=0,j=0}^{1,n} des bases B̃_{k} vérifient

e_{j,0}^{k+1}(x) = e_{j,0}^{k}(x) + (α_{k+n} − α_{k+n−j})e_{j−1,1}^{k}(x) + (β_{k+n} − β_{k+n−j})e_{j−1,0}^{k}(x)
e_{j,1}^{k+1}(x) = e_{j,1}^{k}(x) + (α_{k+n} − α_{k+n−j})e_{j,0}^{k}(x) + [(β_{k+n} − β_{k+n−j}) − (α_{k+n} − α_{k+n−j})α_{k+n−j}]e_{j−1,1}^{k}(x)
−(α_{k+n} − α_{k+n−j})β_{k+n−j}e_{j−1,0}^{k}(x)

pour j = 0, 1, 2, ..., n. Démonstration. Lorsque j ≥ 1 on a

e_{j,0}^{k+1}(x) = (x^{2} + α_{k+n}x + β_{k+n})e_{j−1,0}^{k}(x)
= (x^{2} + α_{k+n−j}x + β_{k+n−j})e_{j−1,0}^{k}(x) + [(α_{k+n} − α_{k+n−j})x + (β_{k+n} − β_{k+n−j})]e_{j−i,0}^{k}(x)
= e_{j,0}^{k}(x) + (α_{k+n} − α_{k+n−j})xe_{j−1,0}^{k}(x) + (β_{k+n} − β_{k+n−j})e_{j−1,0}^{k}(x)
= e_{j,0}^{k}(x) + (α_{k+n} − α_{k+n−j})e_{j−1,1}^{k}(x) + (β_{k+n} − β_{k+n−j})e_{j−1,0}^{k}(x).

Aussi

xe_{j−1,1}^{k}(x) = x^{2}e_{j−1,0}^{k}(x)
= (x^{2} + α_{k+n−j}x + β_{k+n−j})e_{j−1,0}^{k}(x) − (α_{k+n−j}x + β_{k+n−j})e_{j−1,0}^{k}(x)
= e_{j,0}^{k}(x) − α_{k+n−j}e_{j−1,1}^{k}(x) − β_{k+n−j}e_{j−1,0}^{k}(x).

et alors

e_{j,1}^{k+1}(x) = xe_{j,0}^{k+1}(x)
= xe_{j,0}^{k}(x) + (α_{k+n} − α_{k+n−j})xe_{j−1,1}^{k}(x) + (β_{k+n} − β_{k+n−j})xe_{j−1,0}^{k}(x)
= e_{j,1}^{k}(x) + (α_{k+n} − α_{k+n−j})[e_{j,0}^{k}(x) − α_{k+n−j}e_{j−1,1}^{k}(x) − β_{k+n−j}e_{j−1,0}^{k}(x)]
+(β_{k+n} − β_{k+n−j})e_{j−1,1}^{k}(x)
= e_{j,1}^{k}(x) + (α_{k+n} − α_{k+n−j})e_{j,0}^{k}(x) + [(β_{k+n} − β_{k+n−j}) − (α_{k+n} − α_{k+n−j})α_{k+n−j}]e_{j−1,1}^{k}(x)
−(α_{k+n} − α_{k+n−j})β_{k+n−j}e_{j−1,0}^{k}(x). □

En posant [e^{k}(x)]^{T} = [e_{0,0}^{k+1}(x), e_{0,1}^{k+1}(x), e_{1,0}^{k+1}(x), e_{1,1}^{k+1}(x), ..., e_{n,0}^{k+1}(x), e_{n,1}^{k+1}(x)]^{T}, nous avons

[e^{k+1}(x)]^{T} = [e^{k}(x)]^{T} P̃_{k,k+1}

où la matrice de changement de base P_{k,k+1} est donnée par

P̃_{k,k+1} = [\begin{matrix}D_{0}^{k} & A_{1}^{k} & 0 & ⋯ & 0 \\ 0 & D_{1}^{k} & A_{2}^{k} & & 0 \\ 0 & 0 & D_{2}^{k} & ... & 0 \\ ⋮ & ⋮ & & ... & A_{n}^{k} \\ 0 & 0 & 0 & & D_{n}^{k} \end{matrix} ]

où

D_{j}^{k} = [\begin{matrix}1 & α_{k+n} − α_{k+n−j} \\ 0 & 1 \end{matrix}]

avec

A_{j}^{k} = [\begin{matrix}β_{k+n} − β_{k+n−j} & −β_{k+n−j}(α_{k+n} − α_{k+n−j}) \\ α_{k+n} − α_{k+n−j} & (β_{k+n} − β_{k+n−j}) − α_{k+n−j}(α_{k+n} − α_{k+n−j}) \end{matrix}]
= (β_{k+n} − β_{k+n−j}) [\begin{matrix}1 & 0 \\ 0 & 1 \end{matrix}] + (α_{k+n} − α_{k+n−j}) [\begin{matrix}0 & −β_{k+n−j} \\ 1 & −α_{k+n−j} \end{matrix}]

pour j = 0, 1, 2, ..., n.

Si la représentation d’un polynôme p(x) de ℙ^{2n+1} par rapport à la base B̃_{k} est

p(x) = ∑_{j=0}^{n}[a_{j,0}^{k}e_{j,0}^{k}(x) + a_{j,1}^{k}e_{j,1}^{k}(x)],

en posant [p]_{k}^{T} = [a_{0,0}^{k}, a_{0,1}^{k}, ..., a_{n,0}^{k}, a_{n,1}^{k}]^{T} nous avons

p(x) = [e^{k}(x)]^{T} [p]_{k}.

Ainsi on doit avoir

[e^{k+1}(x)]^{T} [p]_{k+1} = [e^{k}(x)]^{T} P̃_{k,k+1}[p]_{k+1} = [e^{k}(x)]^{T} [p]_{k},

d’où

[p]_{k} = P̃_{k,k+1}[p]_{k+1}.

Si on applique m fois la division synthétique à partir de la base B̃_{k} on passe à la base B̃_{k+m} et on a

[p]_{k} = [ ∏_{l=k}^{k+m−1} P̃_{l,l+1}][p]_{k+m}.

Supposons maintenant que pour un certain m ≥ 1 on a α_{k+m+j} = α_{k+j} et β_{k+m+j} = β_{k+j} pour j = 0, 1, ..., n − 1, alors B̃_{k} = B̃_{k+m}, et comme [p]_{k} = [p]_{k+m} on en déduit

I = ∏_{l=k}^{k+m−1} P̃_{l,l+1}.

Ainsi, comme dans le cas des polynômes de degré 1, le changement de base par cette algorithme peut-être cyclique, c’est-à-dire qu’en effectuant l’algorithme un nombre fini de fois, on peut revenir à la base originale.

4.2. Inversion et factorisation. Les matrices dont on peut trouver l’inverse et le factoriser selon cette méthode ont, dans ce cas-ci, une structure spéciale contrairement au cas décrit à la Section 3. Ces matrices sont bi-diabonales par bloc avec des éléments hors diagonaux de structure spéciale.

Notons un premier résultat de factorisation de P̃_{k,k+1}.

Lemme 4.2. La matrice de passage P̃_{k,k+1} est factorisable en un produit de deux matrices B̃_{k,k+1} et D̃_{k,k+1} de telle sorte que

P̃_{k,k+1} = B̃_{k,k+1}D̃_{k,k+1}

où

B̃_{k,k+1} = [\begin{matrix}I & B_{1}^{k} \\ & I & B_{2}^{k} \\ & & I & ... \\ & & & ... & B_{n}^{k} \\ & & & & I \end{matrix}] et D̃_{k,k+1} = [\begin{matrix}D_{0}^{k} & 0 & 0 & ⋯ & 0 \\ 0 & D_{1}^{k} & 0 & ⋯ & 0 \\ 0 & 0 & D_{2}^{k} & ⋯ & 0 \\ & & ... & ... \\ 0 & 0 & 0 & 0 & D_{n}^{k} \end{matrix}] .

avec

B_{j}^{k} = [\begin{matrix}β_{k+n} − β_{k+n−j} & −(α_{k+n} − α_{k+n−j})β_{k+n} \\ α_{k+n} − α_{k+n−j} & (β_{k+n} − β_{k+n−j}) − (α_{k+n} − α_{k+n−j})α_{k+n} \end{matrix}]
= (β_{k+n} − β_{k+n−j}) [\begin{matrix}1 & 0 \\ 0 & 1 \end{matrix}] + (α_{k+n} − α_{k+n−j}) [\begin{matrix}0 & −β_{k+n} \\ 1 & −α_{k+n} \end{matrix}] .

Démonstration. Par un calcul direct on montre que A_{j}^{k} = B_{j}^{k}D_{j}^{k}, d’où le résultat.

□

Les résultats de factorisation de matrices inverses suivent.

Théorème 4.3. Soit

P̃ = [\begin{matrix}D_{0} & A_{1} & 0 & ⋯ & 0 \\ 0 & D_{1} & A_{2} & & 0 \\ 0 & 0 & D_{2} & ... & 0 \\ ⋮ & ⋮ & & ... & A_{n} \\ 0 & 0 & 0 & & D_{n} \end{matrix} ]

avec

D_{j} = [\begin{matrix}1 & a_{j} \\ 0 & 1 \end{matrix}] et A_{j} = b_{j} [\begin{matrix}1 & 0 \\ 0 & 1 \end{matrix}] + a_{j} [\begin{matrix}0 & b_{j} − β \\ 1 & a_{j} − α \end{matrix}]

pour j = 0, 1, 2, ..., n, avec a_{0} = b_{0} = 0. En posant

α_{n−j} = α − a_{j},
β_{n−j} = β − b_{j}

pour j = 0, 1, ..., n, et pour un l ≥ 1

α_{n+l+j} = α_{j},
β_{n+l+j} = β_{j},

pour j = 0, 1, 2, ..., on a B̃_{0} = B̃_{n+l} et

P̃ = P̃_{0,1}  et  P̃^{−1} = ∏_{k=1}^{n+l−1} P̃_{k,k+1}

où la valeur minimale de l est 1. □ Théorème 4.4. La matrice P̃ du théorème précédent se factorise en

P̃ = B̃D̃

où

B̃ = [\begin{matrix}I & B_{1} & 0 & ⋯ & 0 \\ 0 & I & B_{2} & & 0 \\ 0 & 0 & I & ... & 0 \\ ⋮ & ⋮ & & ... & B_{n} \\ 0 & 0 & 0 & & I \end{matrix} ]  et  D̃ = [\begin{matrix}D_{0} & 0 & 0 & ⋯ & 0 \\ 0 & D_{1} & 0 & & 0 \\ 0 & 0 & D_{2} & ... & 0 \\ ⋮ & ⋮ & & ... \\ 0 & 0 & 0 & & D_{n} \end{matrix} ]

avec

B_{j} = b_{j} [\begin{matrix}1 & 0 \\ 0 & 1 \end{matrix}] + a_{j} [\begin{matrix}0 & −β \\ 1 & −α \end{matrix}]

pour j = 0, 1, 2, ..., n. Ainsi en définissant les paires (α_{j}, β_{j}) comme au théorème précédent, nous avons

B̃ = B̃_{0,1} et D̃ = D̃_{0,1}

et

P̃^{−1} = (B̃D̃)^{−1} = ∏_{k=1}^{n+l−1}(B̃_{k,k+1}D̃_{k,k+1})  et  B̃^{−1} = D̃ ∏_{k=1}^{n+l−1}(B̃_{k,k+1}D̃_{k,k+1}),

où la valeur minimale de l est 1. □ 4.3. Exemple. Soit P̃ une (6,6)-matrice construite à partir des valeurs suivantes

\begin{matrix}α = 1, & β = 0, \\ a_{0} = 0, & b_{0} = 0, \\ a_{1} = 1, & b_{1} = −1, \\ a_{2} = 2, & b_{2} = −2, \end{matrix}

alors

\begin{matrix}α_{0} = α − a_{2} = −1, & β_{0} = β − b_{2} = 2, \\ α_{1} = α − a_{1} = 0, & β_{1} = β − b_{1} = 1, \\ α_{2} = α − a_{0} = 1, & β_{2} = β − b_{0} = 0. \end{matrix}

Ainsi on a

P̃ = [\begin{matrix}1 & 0 & −1 & −1 & 0 & 0 \\ 0 & 1 & 1 & −1 & 0 & 0 \\ 0 & 0 & 1 & 1 & −2 & −4 \\ 0 & 0 & 0 & 1 & 2 & 0 \\ 0 & 0 & 0 & 0 & 1 & 2 \\ 0 & 0 & 0 & 0 & 0 & 1 \end{matrix}] .

Alors

B̃ = [\begin{matrix}1 & 0 & −1 & 0 & 0 & 0 \\ 0 & 1 & 1 & −2 & 0 & 0 \\ 0 & 0 & 1 & 0 & −2 & 0 \\ 0 & 0 & 0 & 1 & 2 & −4 \\ 0 & 0 & 0 & 0 & 1 & 0 \\ 0 & 0 & 0 & 0 & 0 & 1 \end{matrix}]  et  D̃ = [\begin{matrix}1 & 0 & 0 & 0 & 0 & 0 \\ 0 & 1 & 0 & 0 & 0 & 0 \\ 0 & 0 & 1 & 1 & 0 & 0 \\ 0 & 0 & 0 & 1 & 0 & 0 \\ 0 & 0 & 0 & 0 & 1 & 2 \\ 0 & 0 & 0 & 0 & 0 & 1 \end{matrix}]

et P̃ = B̃D̃. Les matrices de changement de bases P̃_{k,k+1} pour k = 0, 1, 2 vérifient P̃_{0,1} = P̃ et

P_{1,2} = [\begin{matrix}1 & 0 & 2 & 0 & 0 & 0 \\ 0 & 1 & −2 & 4 & 0 & 0 \\ 0 & 0 & 1 & −2 & 1 & 1 \\ 0 & 0 & 0 & 1 & −1 & 1 \\ 0 & 0 & 0 & 0 & 1 & −1 \\ 0 & 0 & 0 & 0 & 0 & 1 \end{matrix}] et P_{2,3} = [\begin{matrix}1 & 0 & −1 & −2 & 0 & 0 \\ 0 & 1 & 1 & 0 & 0 & 0 \\ 0 & 0 & 1 & 1 & 1 & 0 \\ 0 & 0 & 0 & 1 & −1 & 2 \\ 0 & 0 & 0 & 0 & 1 & −1 \\ 0 & 0 & 0 & 0 & 0 & 1 \end{matrix}]

et

P̃^{−1} = P_{0,1}^{−1} = P_{1,2}P_{2,3}.

Aussi B_{0,1} = B̃, D_{0,1} = D̃ et

B_{1,2} = [\begin{matrix}1 & 0 & 2 & 4 & 0 & 0 \\ 0 & 1 & −2 & 0 & 0 & 0 \\ 0 & 0 & 1 & 0 & 1 & 2 \\ 0 & 0 & 0 & 1 & −1 & 0 \\ 0 & 0 & 0 & 0 & 1 & 0 \\ 0 & 0 & 0 & 0 & 0 & 1 \end{matrix}]  et  D_{1,2} = [\begin{matrix}1 & 0 & 0 & 0 & 0 & 0 \\ 0 & 1 & 0 & 0 & 0 & 0 \\ 0 & 0 & 1 & −2 & 0 & 0 \\ 0 & 0 & 0 & 1 & 0 & 0 \\ 0 & 0 & 0 & 0 & 1 & −1 \\ 0 & 0 & 0 & 0 & 0 & 1 \end{matrix}]

et

B_{2,3} = [\begin{matrix}1 & 0 & −1 & −1 & 0 & 0 \\ 0 & 1 & 1 & −1 & 0 & 0 \\ 0 & 0 & 1 & 0 & 1 & 1 \\ 0 & 0 & 0 & 1 & −1 & 1 \\ 0 & 0 & 0 & 0 & 1 & 0 \\ 0 & 0 & 0 & 0 & 0 & 1 \end{matrix}]  et  D_{2,3} = [\begin{matrix}1 & 0 & 0 & 0 & 0 & 0 \\ 0 & 1 & 0 & 0 & 0 & 0 \\ 0 & 0 & 1 & 1 & 0 & 0 \\ 0 & 0 & 0 & 1 & 0 & 0 \\ 0 & 0 & 0 & 0 & 1 & −1 \\ 0 & 0 & 0 & 0 & 0 & 1 \end{matrix}]

avec

B̃^{−1} = B_{0,1}^{−1} = D_{0,1}(B_{1,2}D_{1,2})(B_{2,3}D_{2,3}).

5. Conclusion

En plus de présenter le cadre vectoriel relié de la division synthétique, nous avons obtenu, par division synthétique avec facteur de degré 1, la factorisation de l’inverse d’une matrice bi-diagonale en un produit de matrices bi-diagonales. De même dans le cas de la division synthétique avec facteur de degré 2, nous avons obtenu la factorisation de l’inverse d’un matrice bi-diagonale par bloc en un produit de matrices bi-diagionales par bloc.

6. Remerciements

Ce travail a été rendu possible grâce au soutien financier provenant du CRSNG (Conseil de recherches en sciences naturelles et en génie du Canada) via une subvention de recherche individuelle du second auteur.

References

[1] R.L. Burden, J.D. Faires et A.C. Reynolds, Numerical Analysis, 2nd Edition, Prindle, Weber and Schmidt, Boston, Massachusetts, 1981.

[2] J.-G. Dion et R. Gaudet, Méthodes d’analyse numérique, Modulo Éditeur, Mont-Royal (Qc), Canada, 1996.

[3] J.V. Uspensky, Theory of Equations, McGraw-Hill book Company, Inc., New-York, Toronto, London, 1948.