ในทางคณิตศาสตร์โดยเฉพาะอย่างยิ่งในการวิเคราะห์เชิงตัวเลขวิธีของ Householderเป็นกลุ่มของอัลกอริทึมการหาค่ารากที่ใช้สำหรับฟังก์ชันของตัวแปรจริงหนึ่งตัวที่มีอนุพันธ์ต่อเนื่องจนถึงอันดับd + 1 แต่ละวิธีเหล่านี้ มีลักษณะเฉพาะด้วยตัวเลขdซึ่งเรียกว่าอันดับของวิธี อัลกอริทึมนี้เป็นแบบวนซ้ำและมีอันดับการลู่เข้าเท่ากับd + 1

วิธีการเหล่านี้ตั้งชื่อตามนักคณิตศาสตร์ชาวอเมริกันอัลสตัน สก็อตต์ เฮาส์โฮลเดอร์กรณีที่d = 1สอดคล้องกับวิธีการของนิวตันและกรณีที่d = 2สอดคล้องกับวิธีการของฮัลลีย์

วิธี Householder เป็นอัลกอริทึมเชิงตัวเลขสำหรับการแก้สมการf ( x ) = 0ในกรณีนี้ ฟังก์ชันfต้องเป็นฟังก์ชันของตัวแปรจริงหนึ่งตัว วิธี^{[ 1 ]}ประกอบด้วยลำดับของการวนซ้ำ

$${\displaystyle x_{n+1}=x_{n}+d\;{\frac {\left(1/f\right)^{(d-1)}(x_{n})}{\left(1/f\right)^{(d)}(x_{n})}}}$$

เริ่มต้นด้วยการคาดเดาค่าเริ่มต้นx โดยที่ตัวเลขยกกำลังในวงเล็บแสดงจำนวนครั้งที่ทำการหาอนุพันธ์ ของฟังก์ชัน

ถ้าfเป็นฟังก์ชันที่หาอนุพันธ์ได้ ต่อเนื่อง d + 1ครั้งและaเป็นศูนย์ของfแต่ไม่ใช่ศูนย์ของอนุพันธ์ของ f แล้ว ในบริเวณใกล้เคียงของaค่าที่ได้จากการวนซ้ำx จะเป็นไปตามเงื่อนไขต่อไปนี้:

$${\displaystyle |x_{n+1}-a|\leq K\cdot {|x_{n}-a|}^{d+1},}$$ สำหรับบางคน${\displaystyle K>0.}$

นี่หมายความว่าค่าที่ได้จากการวนซ้ำจะลู่เข้าสู่ศูนย์หากค่าเริ่มต้นที่คาดเดาไว้ใกล้เคียงเพียงพอ และการลู่เข้าจะมีลำดับd + 1 หรือดีกว่านั้น ยิ่งไปกว่านั้น เมื่อค่าใกล้เคียงกับ aมากพอโดยทั่วไปแล้วมักจะเป็นกรณีที่สำหรับบางค่าโดยเฉพาะอย่างยิ่ง${\displaystyle x_{n+1}-a\approx C(x_{n}-a)^{d+1}}$${\displaystyle C\neq 0}$

• ถ้าdเป็นจำนวนคี่และC > 0การลู่เข้าสู่a จะ มาจากค่าที่มากกว่าa
• ถ้าdเป็นจำนวนคี่และC < 0การลู่เข้าสู่aจะมาจากค่าที่น้อยกว่าa
• ถ้าdเป็นจำนวนคู่และC > 0การลู่เข้าสู่aจะเกิดขึ้นจากด้านที่เริ่มต้น และ
• ถ้าdเป็นจำนวนคู่และC < 0การลู่เข้าสู่aจะสลับข้างกัน

แม้ว่าวิธีการเหล่านี้จะเรียงลำดับการบรรจบกัน แต่ก็ไม่ได้ถูกนำมาใช้กันอย่างแพร่หลายเมื่อd ≥ 3เนื่องจากความแม่นยำที่เพิ่มขึ้นไม่สอดคล้องกับความพยายามที่เพิ่มขึ้นดัชนี Ostrowskiแสดงถึงการลดข้อผิดพลาดในจำนวนการประเมินฟังก์ชันแทนที่จะเป็นจำนวนการวนซ้ำ^{[ 2 ]}

• สำหรับพหุนาม การประเมินค่าอนุพันธ์อันดับแรกdของfที่x โดยใช้วิธีของ Hornerต้องใช้ความพยายาม ในการประเมินพหุนาม d + 1 ครั้งเนื่องจากn ( d + 1)การประเมินค่าในช่วงnรอบจะให้ ค่าเลขชี้กำลัง ของข้อผิดพลาด เท่ากับ ( d + 1) ⁿดังนั้นเลขชี้กำลังสำหรับการประเมินค่าฟังก์ชันหนึ่งครั้ง คือ 1.4142 , 1.4422 , 1.4142 , 1.3797สำหรับd = 1, 2, 3, 4และลดลงหลังจากนั้น ตามเกณฑ์นี้ กรณี d = 2 ( วิธีของ Halley ) คือค่าd ที่เหมาะสม ที่สุด${\displaystyle {\sqrt[{d+1}]{d+1}}}$
• สำหรับฟังก์ชันทั่วไป การประเมินค่าอนุพันธ์โดยใช้เลขคณิตเทย์เลอร์ของการหาอนุพันธ์อัตโนมัติต้องใช้การประเมินค่าฟังก์ชันเทียบเท่ากับ( d + 1)( d + 2)/2 ครั้งการประเมินค่าฟังก์ชันเพียงครั้งเดียวจึงช่วยลดข้อผิดพลาดลงได้ด้วยเลขชี้กำลังซึ่งเป็นค่าสำหรับวิธีของนิวตัน ค่าสำหรับวิธีของฮัลลีย์ และลดลงเข้าใกล้ 1 หรือการลู่เข้าเชิงเส้นสำหรับวิธีลำดับสูงกว่า${\displaystyle {\sqrt[{\frac {(d+1)(d+2)}{2}}]{d+1}}}$${\displaystyle {\sqrt[{3}]{2}}\approx 1.2599}$${\displaystyle {\sqrt[{6}]{3}}\approx 1.2009}$

วิธี Householder อันดับ 1 ก็คือวิธีของนิวตันนั่นเอง เพราะว่า: $${\displaystyle {\begin{array}{rl}x_{n+1}=&x_{n}+1\,{\frac {\left(1/f\right)(x_{n})}{\left(1/f\right)^{(1)}(x_{n})}}\\[.7em]=&x_{n}+{\frac {1}{f(x_{n})}}\cdot \left({\frac {-f'(x_{n})}{f(x_{n})^{2}}}\right)^{-1}\\[.7em]=&x_{n}-{\frac {f(x_{n})}{f'(x_{n})}}.\end{array}}}$$

สำหรับวิธี Householder อันดับ 2 จะได้วิธี Halleyเนื่องจากเอกลักษณ์ และ ผลลัพธ์ ในบรรทัดสุดท้ายคือการปรับปรุงการวนซ้ำของ Newton ณ จุดบรรทัดนี้ถูกเพิ่มเข้ามาเพื่อแสดงให้เห็นว่าความแตกต่างจากวิธี Newton แบบง่ายอยู่ที่ใด$${\displaystyle \textstyle (1/f)'(x)=-{\frac {f'(x)}{f(x)^{2}}}\ }$$$${\displaystyle \textstyle \ (1/f)''(x)=-{\frac {f''(x)}{f(x)^{2}}}+2{\frac {f'(x)^{2}}{f(x)^{3}}}}$$$${\displaystyle {\begin{array}{rl}x_{n+1}=&x_{n}+2\,{\frac {\left(1/f\right)'(x_{n})}{\left(1/f\right)''(x_{n})}}\\[1em]=&x_{n}+{\frac {-2f(x_{n})\,f'(x_{n})}{-f(x_{n})f''(x_{n})+2f'(x_{n})^{2}}}\\[1em]=&x_{n}-{\frac {f(x_{n})f'(x_{n})}{f'(x_{n})^{2}-{\tfrac {1}{2}}f(x_{n})f''(x_{n})}}\\[1em]=&x_{n}+h_{n}\;{\frac {1}{1+{\frac {1}{2}}(f''/f')(x_{n})\,h_{n}}}.\end{array}}}$$${\displaystyle h_{n}=-{\tfrac {f(x_{n})}{f'(x_{n})}}}$${\displaystyle x_{n}}$

วิธีการอันดับที่สามได้มาจากเอกลักษณ์ของอนุพันธ์อันดับที่สามของ1/ f และมีสูตร ดังนี้ เป็นต้น$${\displaystyle \textstyle (1/f)'''(x)=-{\frac {f'''(x)}{f(x)^{2}}}+6{\frac {f'(x)\,f''(x)}{f(x)^{3}}}-6{\frac {f'(x)^{3}}{f(x)^{4}}}}$$$${\displaystyle {\begin{array}{rl}x_{n+1}=&x_{n}+3\,{\frac {\left(1/f\right)''(x_{n})}{\left(1/f\right)'''(x_{n})}}\\[1em]=&x_{n}-{\frac {6f(x_{n})\,f'(x_{n})^{2}-3f(x_{n})^{2}f''(x_{n})}{6f'(x_{n})^{3}-6f(x_{n})f'(x_{n})\,f''(x_{n})+f(x_{n})^{2}\,f'''(x_{n})}}\\[1em]=&x_{n}+h_{n}{\frac {1+{\frac {1}{2}}(f''/f')(x_{n})\,h_{n}}{1+(f''/f')(x_{n})\,h_{n}+{\frac {1}{6}}(f'''/f')(x_{n})\,h_{n}^{2}}}\end{array}}}$$

ปัญหาแรกที่นิวตันแก้ได้ด้วยวิธีนิวตัน-ราฟสัน-ซิมป์สัน คือสมการพหุนามเขาพบว่าควรมีคำตอบที่ใกล้เคียงกับ 2 การแทนที่y = x + 2จะเปลี่ยนสมการเป็น อนุกรมเทย์เลอร์ของฟังก์ชันผกผันเริ่มต้นด้วย ผลลัพธ์ของการประยุกต์ใช้วิธีของเฮาส์โฮลเดอร์ในลำดับต่างๆ ที่x = 0ได้มาจากการหารสัมประสิทธิ์ที่อยู่ติดกันของอนุกรมกำลัง ดังกล่าว สำหรับลำดับแรกๆ จะได้ค่าต่อไปนี้หลังจากขั้นตอนการวนซ้ำเพียงครั้งเดียว: ตัวอย่างเช่น ในกรณีของลำดับที่ 3 .${\displaystyle y^{3}-2y-5=0}$$${\displaystyle 0=f(x)=-1+10x+6x^{2}+x^{3}}$$$${\displaystyle {\begin{array}{rl}1/f(x)=&-1-10\,x-106\,x^{2}-1121\,x^{3}-11856\,x^{4}-125392\,x^{5}\\&-1326177\,x^{6}-14025978\,x^{7}-148342234\,x^{8}-1568904385\,x^{9}\\&-16593123232\,x^{10}+O(x^{11})\end{array}}}$$${\displaystyle x_{1}=0.0+106/1121=0.09455842997324}$

ดังที่เห็นได้ มีทศนิยมที่ถูกต้องมากกว่า d ตำแหน่ง เล็กน้อยสำหรับแต่ละลำดับ d ตัวเลขหนึ่งร้อยหลักแรกของคำตอบที่ถูกต้องคือ0.09455 14815 42326 59148 23865 40579 30296 38573 06105 62823 91803 04128 52904 53121 89983 48366 71462 67281 77715 77578

มาคำนวณค่าสำหรับลำดับต่ำสุดบางค่ากัน${\displaystyle x_{2},x_{3},x_{4}}$

$${\displaystyle f=-1+10x+6x^{2}+x^{3}}$$$${\displaystyle f^{\prime }=10+12x+3x^{2}}$$$${\displaystyle f^{\prime \prime }=12+6x}$$$${\displaystyle f^{\prime \prime \prime }=6}$$

และใช้ความสัมพันธ์ต่อไปนี้

ลำดับที่ 1;${\displaystyle x_{i+1}=x_{i}-f(x_{i})/f^{\prime }(x_{i})}$

ลำดับที่ 2;${\displaystyle x_{i+1}=x_{i}-2ff^{\prime }/(2{f^{\prime }}^{2}-ff^{\prime \prime })}$

ลำดับที่ 3;${\displaystyle x_{i+1}=x_{i}-(6f{f^{\prime }}^{2}-3f^{2}f^{\prime \prime })/(6{f^{\prime }}^{3}-6ff^{\prime }f^{\prime \prime }+f^{2}f^{\prime \prime \prime })}$

การพิสูจน์อย่างแม่นยำของวิธีการของ Householder เริ่มต้นจากการประมาณค่า Padéอันดับd + 1ของฟังก์ชัน โดยเลือกตัวประมาณค่า ที่มีตัวเศษเป็นเชิงเส้น เมื่อทำเช่นนี้ได้แล้ว การปรับปรุงสำหรับการประมาณค่าครั้งต่อไปจะมาจากการคำนวณหาค่าศูนย์ที่ไม่ซ้ำกันของตัวเศษ

การประมาณค่าแบบ Padé มีรูปแบบดังนี้ ฟังก์ชันตรรกยะมีจุดศูนย์ที่$${\displaystyle f(x+h)={\frac {a_{0}+h}{b_{0}+b_{1}h+\cdots +b_{d-1}h^{d-1}}}+O(h^{d+1}).}$$${\displaystyle h=-a_{0}}$

เช่นเดียวกับพหุนามเทย์เลอร์ดีกรีdที่มี สัมประสิทธิ์ d + 1ตัวที่ขึ้นอยู่กับฟังก์ชันfการประมาณค่าแบบ Padé ก็มี สัมประสิทธิ์ d + 1ตัวที่ขึ้นอยู่กับfและอนุพันธ์ของ f เช่นกัน กล่าวคือ ในการประมาณค่าแบบ Padé ใดๆ ดีกรีของพหุนามตัวเศษและตัวส่วนจะต้องรวมกันได้เท่ากับอันดับของการประมาณค่า ดังนั้น จึงต้องเป็นจริง${\displaystyle b_{d}=0}$

เราสามารถหาค่าประมาณของ Padé ได้โดยเริ่มจากพหุนามเทย์เลอร์ของfโดยใช้อัลกอริทึมของยูคลิดอย่างไรก็ตาม การเริ่มต้นจากพหุนามเทย์เลอร์ของ1/ fนั้นสั้นกว่าและนำไปสู่สูตรที่กำหนดโดยตรง เนื่องจาก ต้อง เท่ากับส่วนกลับของฟังก์ชันตรรกยะที่ต้องการ เราจึงได้สมการหลังจากคูณด้วย กำลัง$${\displaystyle (1/f)(x+h)=(1/f)(x)+(1/f)'(x)h+\cdots +(1/f)^{(d-1)}(x){\frac {h^{d-1}}{(d-1)!}}+(1/f)^{(d)}(x){\frac {h^{d}}{d!}}+O(h^{d+1})}$$${\displaystyle a_{0}+h}$${\displaystyle h^{d}}$$${\displaystyle 0=b_{d}=a_{0}(1/f)^{(d)}(x){\frac {1}{d!}}+(1/f)^{(d-1)}(x){\frac {1}{(d-1)!}}}$$

เมื่อแก้สมการสุดท้ายเพื่อหาค่าศูนย์ของตัวเศษ จะได้ผลลัพธ์เป็น .${\displaystyle h=-a_{0}}$$${\displaystyle {\begin{aligned}h&=-a_{0}={\frac {{\frac {1}{(d-1)!}}(1/f)^{(d-1)}(x)}{{\frac {1}{d!}}(1/f)^{(d)}(x)}}\\&=d\,{\frac {(1/f)^{(d-1)}(x)}{(1/f)^{(d)}(x)}}\end{aligned}}}$$

นี่หมายถึงสูตรการวน ซ้ำ$${\displaystyle x_{n+1}=x_{n}+d\;{\frac {\left(1/f\right)^{(d-1)}(x_{n})}{\left(1/f\right)^{(d)}(x_{n})}}}$$

วิธีของ Householder ที่ใช้กับฟังก์ชันค่าจริงf ( x )นั้นเหมือนกับการใช้วิธีของ Newton ในการหาค่าศูนย์ของฟังก์ชัน โดยที่เราคำนวณ อนุพันธ์อันดับที่ ( d − 1)แล้วยกกำลังด้วย−1/ dโดยเฉพาะอย่างยิ่งd = 1จะได้วิธีของ Newton โดยไม่เปลี่ยนแปลง และd = 2จะได้วิธีของ Halley$${\displaystyle x_{n+1}=x_{n}-{\frac {g(x_{n})}{g'(x_{n})}}}$$$${\displaystyle g(x)=\left|(1/f)^{(d-1)}\right|^{-1/d}\,,}$$

• Sebah, Pascal; Gourdon, Xavier (2001). "วิธีการของนิวตันและการวนซ้ำลำดับสูง" . สืบค้นเมื่อ5 พฤศจิกายน 2025 .หมายเหตุ : โปรดใช้ ลิงก์เวอร์ชัน PostScriptเนื่องจากเวอร์ชันบนเว็บไซต์ไม่ได้รับการคอมไพล์อย่างถูกต้อง
• ไวส์สไตน์, เอริค ดับเบิลยู. "วิธีของเฮาส์โฮลเดอร์" . แมธเวิลด์ .