การเรียกซ้ำของเลวินสันหรือการเรียกซ้ำของเลวินสัน-เดอร์บินเป็นกระบวนการในพีชคณิตเชิงเส้นเพื่อคำนวณหาคำตอบของสมการที่เกี่ยวข้องกับเมทริกซ์โทปลิตซ์แบบเรียกซ้ำอัลกอริทึมนี้ทำงานใน เวลา Θ ( n² ⁾ซึ่งเป็นการปรับปรุงที่ดีกว่าการกำจัดแบบเกาส์-จอร์แดนซึ่งทำงานในเวลาΘ ( n³ ) ^{อย่าง}มาก

อั ลกอริทึม Levinson–Durbin ถูกเสนอครั้งแรกโดยNorman Levinsonในปี 1947 ได้รับการปรับปรุงโดยJames Durbinในปี 1960 และต่อมาได้รับการปรับปรุงให้สามารถคูณด้วย^{4n² และ} 3n²โดยWF Trench และ S. Zohar ตามลำดับ

วิธีการประมวลผลข้อมูลอื่นๆ ได้แก่การแยกส่วนแบบ Schurและการแยกส่วนแบบ Cholesky เมื่อเปรียบเทียบกับวิธีการเหล่านี้ การเรียกซ้ำแบบ Levinson (โดยเฉพาะการเรียกซ้ำแบบ Levinson ที่แยกส่วน) มักจะเร็วกว่าในเชิง การ คำนวณ แต่มีความไวต่อความไม่แม่นยำในการคำนวณมากกว่า เช่นข้อผิดพลาดจากการปัดเศษ

อัลกอริทึม Bareiss สำหรับเมทริกซ์ Toeplitz (อย่าสับสนกับอัลกอริทึม Bareiss ทั่วไป ) ทำงานได้เร็วพอๆ กับการเรียกซ้ำของ Levinson แต่ใช้ พื้นที่ O ( n² )ในขณะที่การเรียกซ้ำของ Levinson ใช้พื้นที่เพียงO ( n ) เท่านั้น อย่างไรก็ตาม อัลกอริทึม Bareiss มีเสถียรภาพเชิงตัวเลข [ ^{1 ] [ 2 ] ในขณะที่ การ}เรียกซ้ำของ Levinson มีเสถียรภาพอย่างอ่อนที่สุด (กล่าวคือ มีเสถียรภาพเชิงตัวเลขสำหรับ ระบบ ^เชิง เส้น ที่มีเงื่อนไขดี ) ^{[ 3 ]}

อัลกอริทึมใหม่ที่เรียกว่าอัลกอริทึม Toeplitz ที่เร็วเชิงอะ ซิมโทติก หรือบางครั้ง เรียกว่าอัลกอริทึม Toeplitz ที่เร็วมาก สามารถแก้ปัญหาได้ใน Θ( n (log n ) ^p )สำหรับp ต่างๆ (เช่นp = 2, ^{[ 4 ] [ 5 ]} p = 3 ^{[ 6 ]} ) การเรียกซ้ำของ Levinson ยังคงเป็นที่นิยมด้วยเหตุผลหลายประการ ประการแรกคือเข้าใจได้ง่ายกว่าเมื่อเปรียบเทียบกัน ประการที่สองคือเร็วกว่าอัลกอริทึมที่เร็วมากสำหรับn ขนาดเล็ก (โดยปกติn  < 256) ^{[ 7 ]}

สมการเมทริกซ์มีรูปแบบดังนี้

${\displaystyle \mathbf {M} \,{\vec {x}}={\vec {y}}.}$

อัลกอริทึม Levinson–Durbin สามารถใช้ได้กับสมการใดๆ ก็ตาม ตราบใดที่Mเป็นเมทริกซ์ Toeplitz ที่ทราบค่าและมีค่าใน แนวทแยงหลักไม่เป็นศูนย์ โดยที่เป็นเวกเตอร์ ที่ทราบค่า และเป็นเวกเตอร์ตัวเลขที่ไม่ทราบค่าx _iที่ยังไม่ได้กำหนด ${\displaystyle {\vec {y}}}$${\displaystyle {\vec {x}}}$

ในบทความนี้ê _iคือเวกเตอร์ที่ประกอบด้วยศูนย์ทั้งหมด ยกเว้นตำแหน่งที่iซึ่งมีค่าเป็นหนึ่ง ความยาวของเวกเตอร์จะถูกกำหนดโดยปริยายจากบริบทโดยรอบ คำว่าNหมายถึงความกว้างของเมทริกซ์ข้างต้น – Mคือ เมทริกซ์ขนาด N × Nสุดท้ายนี้ ในบทความนี้ ตัวยกหมายถึงดัชนีแบบอุปนัยในขณะที่ตัวห้อยหมายถึงดัชนี ตัวอย่างเช่น (และคำจำกัดความ) ในบทความนี้ เมทริกซ์T ⁿคือ เมทริกซ์ขนาด n × n ที่คัดลอกบล็อก ขนาด n × nด้านบนซ้ายจากM  – นั่นคือT ⁿ _ij = M _ij

T ⁿก็เป็นเมทริกซ์ Toeplitz เช่นกัน ซึ่งหมายความว่าสามารถเขียนได้ดังนี้

${\displaystyle \mathbf {T} ^{n}={\begin{bmatrix}t_{0}&t_{-1}&t_{-2}&\dots &t_{-n+1}\\t_{1}&t_{0}&t_{-1}&\dots &t_{-n+2}\\t_{2}&t_{1}&t_{0}&\dots &t_{-n+3}\\\vdots &\vdots &\vdots &\ddots &\vdots \\t_{n-1}&t_{n-2}&t_{n-3}&\dots &t_{0}\end{bmatrix}}.}$

อัลกอริทึมนี้ดำเนินการในสองขั้นตอน ในขั้นตอนแรก จะมีการสร้างชุดเวกเตอร์สองชุด เรียกว่า เวกเตอร์ ไปข้างหน้าและ เวกเตอร์ ย้อนกลับเวกเตอร์ไปข้างหน้าใช้เพื่อช่วยในการสร้างชุดเวกเตอร์ย้อนกลับ จากนั้นสามารถทิ้งได้ทันที ส่วนเวกเตอร์ย้อนกลับนั้นจำเป็นสำหรับขั้นตอนที่สอง ซึ่งจะใช้ในการสร้างคำตอบที่ต้องการ

การเรียกซ้ำแบบ Levinson–Durbin กำหนดให้"เวกเตอร์ไปข้างหน้า" ตัวที่n ซึ่งแทนด้วย เป็นเวกเตอร์ที่มีความยาวnซึ่งสอดคล้องกับเงื่อนไขต่อไปนี้: ${\displaystyle {\vec {f}}^{n}}$

${\displaystyle \mathbf {T} ^{n}{\vec {f}}^{n}={\hat {e}__{1}.}$

เวกเตอร์ย้อนกลับตัวที่nถูกกำหนดในทำนองเดียวกัน โดยเป็นเวกเตอร์ที่มีความยาวnซึ่งสอดคล้องกับเงื่อนไขต่อไปนี้: ${\displaystyle {\vec {b}}^{n}}$

${\displaystyle \mathbf {T} ^{n}{\vec {b}}^{n}={\hat {e}__{n}.}$

การลดความซับซ้อนที่สำคัญสามารถเกิดขึ้นได้เมื่อMเป็นเมทริกซ์สมมาตร ในกรณี นี้ เวกเตอร์ทั้งสองจะมีความสัมพันธ์กันโดยb ⁿ _i = f ⁿ _{n +1− i} – กล่าวคือ เวกเตอร์ทั้งสองเป็นการสลับแถวของกันและกัน ซึ่งสามารถช่วยลดการคำนวณเพิ่มเติมในกรณีพิเศษนี้ได้

แม้ว่าเมทริกซ์จะไม่สมมาตร เวกเตอร์ไปข้างหน้าและย้อนกลับลำดับที่ nก็สามารถหาได้จากเวกเตอร์ที่มีความยาวn  − 1 ดังต่อไปนี้ ขั้นแรก เวกเตอร์ไปข้างหน้าอาจถูกขยายด้วยศูนย์เพื่อให้ได้:

${\displaystyle \mathbf {T} ^{n}{\begin{bmatrix}{\vec {f}}^{n-1}\\0\\\end{bmatrix}}={\begin{bmatrix}\ &\ &\ &t_{-n+1}\\\ &\mathbf {T} ^{n-1}&\ &t_{-n+2}\\\ &\ &\ &\vdots \\t_{n-1}&t_{n-2}&\dots &t_{0}\\\end{bmatrix}}{\begin{bmatrix}\ \\{\vec {f}}^{n-1}\\\ \\0\\\ \\\end{bmatrix}}={\begin{bmatrix}1\\0\\\vdots \\0\\\varepsilon _{f}^{n}\end{bmatrix}}.}$

ในการเปลี่ยนจากT ^{n −1}ไปเป็นT ⁿคอลัมน์พิเศษที่เพิ่มเข้าไปในเมทริกซ์จะไม่รบกวนคำตอบเมื่อใช้ศูนย์เพื่อขยายเวกเตอร์ไปข้างหน้า อย่างไรก็ตามแถว พิเศษ ที่เพิ่มเข้าไปในเมทริกซ์ได้รบกวนคำตอบ และสร้างพจน์ความคลาดเคลื่อนที่ไม่ต้องการε _fซึ่งเกิดขึ้นในตำแหน่งสุดท้าย สมการข้างต้นให้ค่าของมันดังนี้:

${\displaystyle \varepsilon _{f}^{n}\ =\ \sum _{i=1}^{n-1}\ M_{ni}\ f_{i}^{n-1}\ =\ \sum _{i=1}^{n-1}\ t_{n-i}\ f_{i}^{n-1}.}$

ข้อผิดพลาดนี้จะถูกส่งกลับมาในไม่ช้าและจะถูกกำจัดออกจากเวกเตอร์ไปข้างหน้าตัวใหม่ แต่ก่อนอื่น เวกเตอร์ย้อนกลับจะต้องถูกขยายในลักษณะเดียวกัน (แม้ว่าจะกลับทิศทางก็ตาม) สำหรับเวกเตอร์ย้อนกลับนั้น

${\displaystyle \mathbf {T} ^{n}{\begin{bmatrix}0\\{\vec {b}}^{n-1}\\\end{bmatrix}}={\begin{bmatrix}t_{0}&\dots &t_{-n+2}&t_{-n+1}\\\vdots &\ &\ &\ \\t_{n-2}&\ &\mathbf {T} ^{n-1}&\ \\t_{n-1}&\ &\ &\end{bmatrix}}{\begin{bmatrix}\ \\0\\\ \\{\vec {b}}^{n-1}\\\ \\\end{bmatrix}}={\begin{bmatrix}\varepsilon _{b}^{n}\\0\\\vdots \\0\\1\end{bmatrix}}.}$

เช่นเดียวกับก่อนหน้านี้ คอลัมน์พิเศษที่เพิ่มเข้าไปในเมทริกซ์ไม่ได้รบกวนเวกเตอร์ย้อนกลับใหม่นี้ แต่แถวพิเศษกลับรบกวน ในกรณีนี้ เรามีข้อผิดพลาดที่ไม่ต้องการอีกค่าหนึ่งคือε _bซึ่งมีค่าดังนี้:

${\displaystyle \varepsilon _{b}^{n}\ =\ \sum _{i=2}^{n}\ M_{1i}\ b_{i-1}^{n-1}\ =\ \sum _{i=1}^{n-1}\ t_{-i}\ b_{i}^{n-1}.\ }$

พจน์ความคลาดเคลื่อนทั้งสองนี้สามารถนำมาใช้สร้างเวกเตอร์ไปข้างหน้าและย้อนกลับลำดับสูงกว่าได้ดังที่อธิบายไว้ต่อไปนี้ โดยใช้คุณสมบัติความเป็นเชิงเส้นของเมทริกซ์ เอกลักษณ์ต่อไปนี้จึงเป็นจริงสำหรับทุกค่า: ${\displaystyle (\alpha ,\beta )}$

${\displaystyle \mathbf {T} \left(\alpha {\begin{bmatrix}{\vec {f}}\\\ \\0\\\end{bmatrix}}+\beta {\begin{bmatrix}0\\\ \\{\vec {b}}\end{bmatrix}}\right)=\alpha {\begin{bmatrix}1\\0\\\vdots \\0\\\varepsilon _{f}\\\end{bmatrix}}+\beta {\begin{bmatrix}\varepsilon _{b}\\0\\\vdots \\0\\1\end{bmatrix}}.}$

ถ้า เลือกค่า αและβให้ด้านขวามือได้ผลลัพธ์เป็นê ₁หรือê _nแล้ว ปริมาณในวงเล็บจะตรงตามนิยามของ เวกเตอร์ไปข้างหน้าหรือเวกเตอร์ย้อนกลับลำดับที่ nตามลำดับ เมื่อเลือกค่า α และ β แล้ว ผลรวมเวกเตอร์ในวงเล็บจะง่ายและให้ผลลัพธ์ที่ต้องการ

ในการหาค่าสัมประสิทธิ์เหล่านี้จะต้องเป็นไปตามเงื่อนไขดังต่อไปนี้: ${\displaystyle \alpha _{f}^{n}}$${\displaystyle \beta _{f}^{n}}$

${\displaystyle {\vec {f}}^{n}=\alpha _{f}^{n}{\begin{bmatrix}{\vec {f}}^{n-1}\\0\end{bmatrix}}+\beta _{f}^{n}{\begin{bmatrix}0\\{\vec {b}}^{n-1}\end{bmatrix}}}$

และตามลำดับ มีคุณสมบัติดังนี้: ${\displaystyle \alpha _{b}^{n}}$${\displaystyle \beta _{b}^{n}}$

${\displaystyle {\vec {b}}^{n}=\alpha _{b}^{n}{\begin{bmatrix}{\vec {f}}^{n-1}\\0\end{bmatrix}}+\beta _{b}^{n}{\begin{bmatrix}0\\{\vec {b}}^{n-1}\end{bmatrix}}.}$

เมื่อคูณสมการทั้งสองก่อนหน้านี้ด้วยหนึ่ง จะได้สมการต่อไปนี้: ${\displaystyle {\mathbf {T} }^{n}}$

${\displaystyle {\begin{bmatrix}1&\varepsilon _{b}^{n}\\0&0\\\vdots &\vdots \\0&0\\\varepsilon _{f}^{n}&1\end{bmatrix}}{\begin{bmatrix}\alpha _{f}^{n}&\alpha _{b}^{n}\\\beta _{f}^{n}&\beta _{b}^{n}\end{bmatrix}}={\begin{bmatrix}1&0\\0&0\\\vdots &\vdots \\0&0\\0&1\end{bmatrix}}.}$

เมื่อตัดค่าศูนย์ทั้งหมดที่อยู่ตรงกลางของเวกเตอร์ทั้งสองข้างต้นออกไปแล้ว จะเหลือเพียงสมการต่อไปนี้:

${\displaystyle {\begin{bmatrix}1&\varepsilon _{b}^{n}\\\varepsilon _{f}^{n}&1\end{bmatrix}}{\begin{bmatrix}\alpha _{f}^{n}&\alpha _{b}^{n}\\\beta _{f}^{n}&\beta _{b}^{n}\end{bmatrix}}={\begin{bmatrix}1&0\\0&1\end{bmatrix}}.}$

เมื่อแก้สมการเหล่านี้แล้ว (โดยใช้สูตร เมทริกซ์ผกผัน 2×2 ของ Cramer ) เวกเตอร์ไปข้างหน้าและย้อนกลับใหม่จะเป็นดังนี้:

${\displaystyle {\vec {f}}^{n}={1 \over {1-\varepsilon _{b}^{n}\varepsilon _{f}^{n}}}{\begin{bmatrix}{\vec {f}}^{n-1}\\0\end{bmatrix}}-{\varepsilon _{f}^{n} \over {1-\varepsilon _{b}^{n}\varepsilon _{f}^{n}}}{\begin{bmatrix}0\\{\vec {b}}^{n-1}\end{bmatrix}}}$

${\displaystyle {\vec {b}}^{n}={1 \over {1-\varepsilon _{b}^{n}\varepsilon _{f}^{n}}}{\begin{bmatrix}0\\{\vec {b}}^{n-1}\end{bmatrix}}-{\varepsilon _{b}^{n} \over {1-\varepsilon _{b}^{n}\varepsilon _{f}^{n}}}{\begin{bmatrix}{\vec {f}}^{n-1}\\0\end{bmatrix}}.}$

เมื่อทำการบวกเวกเตอร์เหล่านี้แล้ว จะได้ เวกเตอร์ไปข้างหน้าและย้อนกลับลำดับที่ nจากเวกเตอร์ก่อนหน้า สิ่งที่เหลืออยู่ก็คือการหาเวกเตอร์ตัวแรกในกลุ่มนี้ จากนั้นทำการบวกและคูณอย่างรวดเร็วเพื่อหาเวกเตอร์ที่เหลือ เวกเตอร์ไปข้างหน้าและย้อนกลับตัวแรกมีดังนี้:

${\displaystyle {\vec {f}}^{1}={\vec {b}}^{1}=\left[{1 \over M_{11}}\right]=\left[{1 \over t_{0}}\right].}$

ขั้นตอนข้างต้นจะให้ เวกเตอร์ย้อนกลับ NตัวสำหรับMจากนั้นจะได้สมการที่กำหนดขึ้นเองได้ดังนี้:

${\displaystyle {\vec {y}}=\mathbf {M} \ {\vec {x}}.}$

วิธีแก้ปัญหาสามารถสร้างขึ้นได้ในลักษณะการเรียกซ้ำแบบเดียวกับที่สร้างเวกเตอร์ย้อนกลับ ดังนั้นจะต้องขยายไปสู่ลำดับของตัวกลางโดย ที่${\displaystyle {\vec {x}}}$${\displaystyle {\vec {x}}^{n}}$${\displaystyle {\vec {x}}^{N}={\vec {x}}}$

จากนั้นจึงสร้างวิธีแก้ปัญหาแบบเรียกซ้ำโดยสังเกตว่าถ้า

${\displaystyle \mathbf {T} ^{n-1}{\begin{bmatrix}x_{1}^{n-1}\\x_{2}^{n-1}\\\vdots \\x_{n-1}^{n-1}\\\end{bmatrix}}={\begin{bmatrix}y_{1}\\y_{2}\\\vdots \\y_{n-1}\end{bmatrix}}.}$

จากนั้นขยายด้วยเลขศูนย์อีกครั้ง และกำหนดค่าคงที่ความคลาดเคลื่อนเมื่อจำเป็น:

${\displaystyle \mathbf {T} ^{n}{\begin{bmatrix}x_{1}^{n-1}\\x_{2}^{n-1}\\\vdots \\x_{n-1}^{n-1}\\0\end{bmatrix}}={\begin{bmatrix}y_{1}\\y_{2}\\\vdots \\y_{n-1}\\\varepsilon _{x}^{n-1}\end{bmatrix}}.}$

จากนั้นเราสามารถใช้ เวกเตอร์ย้อนกลับลำดับที่ nเพื่อกำจัดพจน์ความคลาดเคลื่อนและแทนที่ด้วยสูตรที่ต้องการได้ดังนี้:

${\displaystyle \mathbf {T} ^{n}\left({\begin{bmatrix}x_{1}^{n-1}\\x_{2}^{n-1}\\\vdots \\x_{n-1}^{n-1}\\0\\\end{bmatrix}}+(y_{n}-\varepsilon _{x}^{n-1})\ {\vec {b}}^{n}\right)={\begin{bmatrix}y_{1}\\y_{2}\\\vdots \\y_{n-1}\\y_{n}\end{bmatrix}}.}$

การขยายวิธีการนี้ไปจนถึงn = Nจะได้คำตอบ ${\displaystyle {\vec {x}}}$

ในทางปฏิบัติ ขั้นตอนเหล่านี้มักจะดำเนินการไปพร้อม ๆ กับขั้นตอนอื่น ๆ แต่ขั้นตอนเหล่านี้ประกอบกันเป็นหน่วยที่สอดคล้องกันและสมควรได้รับการพิจารณาเป็นขั้นตอนแยกต่างหาก

ถ้าMไม่ใช่เมทริกซ์ Toeplitz อย่างแท้จริง แต่เป็นเมทริกซ์ Toeplitz แบบบล็อก การเรียกซ้ำของ Levinson สามารถหาได้ในลักษณะเดียวกันโดยพิจารณาเมทริกซ์ Toeplitz แบบบล็อกว่าเป็นเมทริกซ์ Toeplitz ที่มีองค์ประกอบเมทริกซ์ (Musicus 1988) เมทริกซ์ Toeplitz แบบบล็อกเกิดขึ้นตามธรรมชาติใน อัลกอริธึม การประมวลผลสัญญาณเมื่อต้องจัดการกับกระแสสัญญาณหลายกระแส (เช่น ใน ระบบ MIMO ) หรือสัญญาณไซโคลสเตชันนารี

• การเรียกซ้ำแบบแยก Levinson
• การทำนายเชิงเส้น
• แบบจำลองอัตถารีเกรสซีฟ