อัลกอริทึม Remezหรืออัลกอริทึมการแลกเปลี่ยน Remezซึ่งเผยแพร่โดยEvgeny Yakovlevich Remezในปี 1934 เป็นอัลกอริทึมแบบวนซ้ำที่ใช้ในการค้นหาการประมาณค่าฟังก์ชันอย่างง่าย โดยเฉพาะอย่างยิ่งการประมาณค่าฟังก์ชันในปริภูมิ Chebyshevที่ดีที่สุดในแง่ของบรรทัดฐานสม่ำเสมอL ^{[ 1 ]}บางครั้งเรียกว่าอัลกอริทึม Remesหรือ อัลกอริ ทึมReme ^{[ 2 ]}

ตัวอย่างทั่วไปของปริภูมิเชบิเชฟคือปริภูมิย่อยของพหุนามเชบิเชฟอันดับnในปริภูมิของฟังก์ชันต่อเนื่อง จริง บนช่วงC [ a , b ] พหุนามประมาณค่าที่ดีที่สุดภายในปริภูมิย่อยที่กำหนดจะถูกนิยามว่าเป็นพหุนามที่ทำให้ผลต่างสัมบูรณ์สูงสุดระหว่างพหุนามกับฟังก์ชันมีค่าน้อยที่สุดในกรณีนี้ รูปแบบของคำตอบจะถูกกำหนดอย่างแม่นยำโดยทฤษฎีบทการแกว่งเท่ากัน

อัลกอริทึม Remez เริ่มต้นด้วยฟังก์ชัน${\displaystyle f}$เพื่อที่จะประมาณค่าและเป็นชุด${\displaystyle X}$ของ${\displaystyle n+2}$ตัวอย่างจุด${\displaystyle x_{1},x_{2},...,x_{n+2}}$ในช่วงการประมาณค่า โดยปกติแล้วค่าสุดขั้วของพหุนามเชบิเชฟจะถูกแปลงเชิงเส้นไปยังช่วงนั้น ขั้นตอนมีดังนี้:

• แก้ระบบสมการเชิงเส้น

${\displaystyle b_{0}+b_{1}x_{i}+...+b_{n}x_{i}^{n}+(-1)^{i}E=f(x_{i})}$(ที่ไหน${\displaystyle i=1,2,...n+2}$),

สำหรับสิ่งที่ไม่รู้${\displaystyle b_{0},b_{1}...b_{n}}$และอี .

• ใช้${\displaystyle b_{i}}$ใช้เป็นสัมประสิทธิ์เพื่อสร้างพหุนาม${\displaystyle P_{n}}$.
• ค้นหาชุด${\displaystyle M}$ของจุดที่มีข้อผิดพลาดสูงสุดเฉพาะที่${\displaystyle |P_{n}(x)-f(x)|}$.
• หากเกิดข้อผิดพลาดในทุกๆ${\displaystyle m\in M}$มีขนาดเท่ากันและสลับเครื่องหมายกัน จากนั้น${\displaystyle P_{n}}$คือพหุนามประมาณค่ามินิแม็กซ์ ถ้าไม่ใช่ ให้แทนที่ด้วย${\displaystyle X}$กับ${\displaystyle M}$และทำซ้ำขั้นตอนข้างต้น

ผลลัพธ์นี้เรียกว่าพหุนามประมาณค่าที่ดีที่สุด หรืออัลกอริธึมการประมาณค่าแบบมินิแม็กซ์

W. Fraser ได้ทำการตรวจสอบรายละเอียดทางเทคนิคในการใช้งานอัลกอริทึม Remez ^{[ 3 ]}

ส่วนนี้ให้ข้อมูลเพิ่มเติมเกี่ยวกับขั้นตอนต่างๆ ที่ได้กล่าวไว้ข้างต้น ในส่วนนี้ ดัชนีiมีค่าตั้งแต่ 0 ถึงn + 1

ขั้นตอนที่ 1:กำหนดให้${\displaystyle x_{0},x_{1},...x_{n+1}}$แก้ระบบสมการเชิงเส้นn + 2 สมการ

${\displaystyle b_{0}+b_{1}x_{i}+...+b_{n}x_{i}^{n}+(-1)^{i}E=f(x_{i})}$(ที่ไหน${\displaystyle i=0,1,...n+1}$),

สำหรับสิ่งที่ไม่รู้${\displaystyle b_{0},b_{1},...b_{n}}$และอี .

ควรจะชัดเจนแล้วว่า${\displaystyle (-1)^{i}E}$สมการนี้จะสมเหตุสมผลก็ต่อเมื่อโหนดต่างๆ${\displaystyle x_{0},...,x_{n+1}}$เรียงลำดับจากน้อยไปมากหรือจากมากไปน้อย ระบบสมการเชิงเส้นนี้จะมีคำตอบเดียว (ดังที่ทราบกันดีว่า ไม่ใช่ทุกระบบสมการเชิงเส้นจะมีคำตอบ) นอกจากนี้ คำตอบนั้นสามารถหาได้โดยใช้เพียง...${\displaystyle O(n^{2})}$การดำเนินการทางคณิตศาสตร์ ในขณะที่ตัวแก้ปัญหามาตรฐานจากไลบรารีจะใช้เวลา${\displaystyle O(n^{3})}$การดำเนินการ นี่คือหลักฐานอย่างง่าย:

คำนวณค่าประมาณเชิงเส้นมาตรฐานระดับn${\displaystyle p_{1}(x)}$ถึง${\displaystyle f(x)}$ที่ โหนด n + 1 แรก และยังรวมถึง ตัวแทรกสอดระดับ nมาตรฐานด้วย${\displaystyle p_{2}(x)}$ถึงพระบรมสารีริกธาตุ${\displaystyle (-1)^{i}}$

${\displaystyle p_{1}(x_{i})=f(x_{i}),p_{2}(x_{i})=(-1)^{i},i=0,...,n.}$

เพื่อจุดประสงค์นี้ ให้ใช้ สูตรการแทรกสอดของนิวตันกับ ผลต่าง หารอันดับในแต่ละครั้ง${\displaystyle 0,...,n}$และ${\displaystyle O(n^{2})}$การดำเนินการทางคณิตศาสตร์

พหุนาม${\displaystyle p_{2}(x)}$มีศูนย์ลำดับที่iอยู่ระหว่าง${\displaystyle x_{i-1}}$และ${\displaystyle x_{i},\ i=1,...,n}$และด้วยเหตุนี้จึงไม่มีเลขศูนย์เพิ่มเติมระหว่างนั้น${\displaystyle x_{n}}$และ${\displaystyle x_{n+1}}$:${\displaystyle p_{2}(x_{n})}$และ${\displaystyle p_{2}(x_{n+1})}$มีสัญลักษณ์เดียวกัน${\displaystyle (-1)^{n}}$.

การรวมเชิงเส้น ${\displaystyle p(x):=p_{1}(x)-p_{2}(x)\!\cdot \!E}$ยังเป็นพหุนามดีกรีn ด้วย และ

${\displaystyle p(x_{i})=p_{1}(x_{i})-p_{2}(x_{i})\!\cdot \!E\ =\ f(x_{i})-(-1)^{i}E,\ \ \ \ i=0,\ldots ,n.}$

นี่คือสมการเดียวกันกับข้างต้นสำหรับ${\displaystyle i=0,...,n}$และสำหรับการเลือกE ใดๆ สมการเดียวกันสำหรับi = n + 1 คือ

${\displaystyle p(x_{n+1})\ =\ p_{1}(x_{n+1})-p_{2}(x_{n+1})\!\cdot \!E\ =\ f(x_{n+1})-(-1)^{n+1}E}$และต้องใช้เหตุผลพิเศษ: เมื่อแก้สมการหาค่าตัวแปรEแล้ว จะได้เป็นนิยามของE นั่นเอง :

${\displaystyle E\$ :=\ {\frac {p_{1}(x_{n+1})-f(x_{n+1})}{p_{2}(x_{n+1})+(-1)^{n}}}.}

ดังที่กล่าวมาข้างต้น พจน์ทั้งสองในตัวส่วนมีเครื่องหมายเดียวกัน คือ Eและดังนั้น${\displaystyle p(x)\equiv b_{0}+b_{1}x+\ldots +b_{n}x^{n}}$มักมีขอบเขตที่ชัดเจนเสมอ

ข้อผิดพลาดที่ โหนดเรียงลำดับ n + 2 ที่กำหนดนั้นมีทั้งค่าบวกและค่าลบตามลำดับ เนื่องจาก

${\displaystyle p(x_{i})-f(x_{i})\ =\ -(-1)^{i}E,\ \ i=0,...,n\!+\!1.}$

ทฤษฎีบทการแกว่งเท่ากันกล่าวว่า ภายใต้เงื่อนไขนี้ จะไม่มีพหุนามดีกรีn ใด ที่มีค่าความคลาดเคลื่อนน้อยกว่าEอันที่จริง หากมีพหุนามดังกล่าวอยู่จริง ให้เรียกมันว่า${\displaystyle {\tilde {p}}(x)}$แล้วความแตกต่างล่ะ ${\displaystyle p(x)-{\tilde {p}}(x)=(p(x)-f(x))-({\tilde {p}}(x)-f(x))}$ค่าที่โหนด n + 2 ยังคงเป็นบวก/ลบอยู่${\displaystyle x_{i}}$และด้วยเหตุนี้จึงมีรากอย่างน้อยn + 1 ตัว ซึ่งเป็นไปไม่ได้สำหรับพหุนามดีกรีnดังนั้นE นี้ จึงเป็นขอบล่างของข้อผิดพลาดขั้นต่ำที่สามารถทำได้ด้วยพหุนามดีกรีn

ขั้นตอนที่ 2เปลี่ยนสัญลักษณ์จาก ${\displaystyle b_{0}+b_{1}x+...+b_{n}x^{n}}$ถึง${\displaystyle p(x)}$.

ขั้นตอนที่ 3ปรับปรุงโหนดอินพุตให้ดียิ่งขึ้น${\displaystyle x_{0},...,x_{n+1}}$และข้อผิดพลาดของพวกเขา${\displaystyle \pm E}$ดังต่อไปนี้

ในแต่ละภูมิภาค P โหนดปัจจุบัน${\displaystyle x_{i}}$ถูกแทนที่ด้วยตัวเพิ่มค่าสูงสุดเฉพาะที่${\displaystyle {\bar {x}}_{i}}$และในแต่ละภูมิภาค N${\displaystyle x_{i}}$ถูกแทนที่ด้วยตัวลดค่าต่ำสุดเฉพาะที่ (คาดหวัง)${\displaystyle {\bar {x}}_{0}}$ที่A​${\displaystyle {\bar {x}}_{i}}$ใกล้${\displaystyle x_{i}}$, และ${\displaystyle {\bar {x}}_{n+1}}$ที่B. ) ไม่จำเป็นต้องมีความแม่นยำสูงที่นี่การค้นหาเส้น มาตรฐาน ด้วยการปรับแบบกำลังสองสองสามแบบ ก็น่าจะเพียงพอแล้ว (ดู^{[ 10 ]} )

อนุญาต${\displaystyle z_{i}:=p({\bar {x}}_{i})-f({\bar {x}}_{i})}$แต่ละแอมพลิจูด${\displaystyle |z_{i}|}$มีค่ามากกว่าหรือเท่ากับEทฤษฎีบทของเดอ ลา วัลเล ปูแซงและการพิสูจน์ก็ใช้ได้กับกรณีนี้เช่นกัน${\displaystyle z_{0},...,z_{n+1}}$กับ${\displaystyle \min\{|z_{i}|\}\geq E}$ถือเป็นขอบเขตล่างใหม่สำหรับ ค่าความคลาดเคลื่อนที่ดีที่สุดที่เป็นไปได้สำหรับพหุนามดีกรีn

นอกจากนี้,${\displaystyle \max\{|z_{i}|\}}$ซึ่งมีประโยชน์อย่างยิ่งในฐานะขอบเขตบนที่ชัดเจนสำหรับข้อผิดพลาดที่ดีที่สุดที่เป็นไปได้

ขั้นตอนที่ 4:ด้วย${\displaystyle \min \,\{|z_{i}|\}}$และ${\displaystyle \max \,\{|z_{i}|\}}$เนื่องจากขอบเขตล่างและขอบเขตบนสำหรับข้อผิดพลาดในการประมาณค่า ที่ดีที่สุดที่เป็นไปได้ จึงมีเกณฑ์การหยุดที่เชื่อถือได้: ทำซ้ำขั้นตอนจนกว่า${\displaystyle \max\{|z_{i}|\}-\min\{|z_{i}|\}}$มีขนาดเล็กพอหรือไม่ลดลงอีกต่อไป ขอบเขตเหล่านี้บ่งชี้ถึงความคืบหน้า

มีการดัดแปลงอัลกอริธึมบางส่วนในเอกสาร^{[ 11 ]}ซึ่งรวมถึง:

• แทนที่จุดตัวอย่างมากกว่าหนึ่งจุดด้วยตำแหน่งของค่าความแตกต่างสัมบูรณ์สูงสุดที่อยู่ใกล้เคียงกัน
• แทนที่จุดตัวอย่างทั้งหมดภายในการวนซ้ำครั้งเดียวด้วยตำแหน่งของความแตกต่างสูงสุดทั้งหมด สลับเครื่องหมาย^{[ 12 ]}
• การใช้ค่าความคลาดเคลื่อนสัมพัทธ์เพื่อวัดความแตกต่างระหว่างค่าประมาณและฟังก์ชัน โดยเฉพาะอย่างยิ่งหากจะใช้ค่าประมาณนั้นในการคำนวณฟังก์ชันบนคอมพิวเตอร์ที่ใช้เลขคณิตแบบจุดลอยตัว
• รวมถึงข้อจำกัดจุดศูนย์ข้อผิดพลาด^{[ 12 ]}
• ตัวแปร Fraser-Hart ใช้เพื่อกำหนดค่าประมาณ Chebyshev เชิงตรรกะที่ดีที่สุด^{[ 13 ]}

• ทฤษฎีบทของฮาดามาร์ด– หน้าเว็บที่แสดงคำอธิบายสั้นๆ โดยไม่มีช่องว่าง 
• ซีรี่ส์ลอเรนต์– ซีรี่ส์พลังที่มีพลังด้านลบ 
• Padé approximant – การประมาณค่าที่ดีที่สุดของฟังก์ชันด้วยฟังก์ชันตรรกยะอันดับที่กำหนด 
• อนุกรมนิวตัน– อนาล็อกแบบไม่ต่อเนื่องของอนุพันธ์ หน้าเว็บที่แสดงคำอธิบายสั้น ๆ ของเป้าหมายการเปลี่ยนเส้นทาง 
• ทฤษฎีการประมาณค่า– ทฤษฎีเกี่ยวกับการหาค่าที่ใกล้เคียงกับความเป็นจริงอย่างยอมรับได้สำหรับการคำนวณทางคณิตศาสตร์ที่ไม่แม่นยำ 
• การประมาณฟังก์ชัน– การประมาณฟังก์ชันใดๆ ด้วยฟังก์ชันที่มีพฤติกรรมที่ดี 

• การประมาณค่าแบบมินิแม็กซ์และอัลกอริธึมของรีเมซบทพื้นฐานใน เอกสารประกอบของ Boost Math Tools พร้อมลิงก์ไปยังการใช้งานในภาษา C++
• บทนำเกี่ยวกับ DSP ( เก็บถาวรเมื่อ 23 เมษายน 2557 ที่Wayback Machine)
• อาร์ทส์, โรนัลด์ เอ็ม. ; บอนด์, ชาร์ลส์; Mendelsohn, Phil & Weisstein, Eric W. "อัลกอริทึม Remez" . แมทเวิลด์ .