- ข้อความ
- ประวัติศาสตร์
1. IntroductionGiven a positive int
1. Introduction
Given a positive integer n and complex numbers ai,bi,i=1,…,n such that bi≠bj for i≠j and ai≠0 for i=1,…,n, consider the rational function
equation(1)
Turn MathJax on
We associate with S(x) the secular equation S(x)=0. The numbers bi and ai, for i=1,…,n are referred to as the nodes and the coefficients of the secular function S(x), respectively.
Equations of this kind are mainly encountered in the case of real nodes bi and positive coefficients ai when the roots are real. Typical examples are modifying symmetric eigenvalue problems [1], or solving the tridiagonal symmetric eigenvalue problem by means of divide and conquer techniques [2] and [3], updating the singular values of a matrix, solving least squares problems [4], invariant subspace computation [5] and more. Over the complex field, for any set of nodes and coefficients, secular equations are encountered in the solution of the eigenvalue problem for a diagonal plus rank-one matrix [6], [7], [8] and [9] and in representing generalized companion matrix pencils in the Lagrange basis especially in the framework of “polynomial algebra by values” [10].
Secular equations are also a powerful tool for attacking the polynomial root-finding problem. This is the main fact that motivates our interest in such equations. In fact, the monic polynomial of degree n
Turn MathJax on
has roots that coincide with the roots of S(x). Moreover, one can verify that
equation(2)
Turn MathJax on
so that, given the polynomial p(x) and the nodes bi it is not expensive to compute the coefficients ai and to reformulate the polynomial root-finding problem in terms of a secular equation.
In this paper we present a method for the numerical solution of secular equations together with its computational analysis. More precisely we describe, analyze and implement an algorithm which, given in input the coefficients ai and the nodes bi,i=1,…,n of the secular function S(x) together with an integer d, provides in output the roots of S(x) represented with d guaranteed digits. In its cheaper version (isolation), the algorithm can provide approximations to the roots with the minimum number of digits sufficient to separate them from each other. The maximum number d of digits is used only for those roots, if any, which cannot be otherwise separated.
The algorithm can be effectively used as a tool for computing an arbitrarily large number d of digits of the roots of a polynomial p(x) assigned either in terms of its coefficients in some polynomial basis or by means of a black box which, given in input a complex number x, provides in output the complex number p(x). In fact we will show that using the representation of a polynomial in terms of secular equation provides substantial computational advantages.
The method relies on the combination of two different strategies to reduce the required precision of the floating point arithmetic: the strategy adopted in the package of MPSolve of D. Bini and G. Fiorentino [11], and that used in the package Eigensolve of S. Fortune [12]. It exploits some theoretical results, that we present in this paper, concerning root-neighborhoods, numerical conditioning, a posteriori error bounds, and rounding error analysis, related to computations with secular functions. It relies also on the formulation of the problem given in terms of structured matrices and on the Ehrlich–Aberth iteration as main approximation engine [13] and [14].
The algorithm that we have obtained has been implemented in the language C and incorporated in the package MPSolve originating the release MPSolve 3.0. The software is free and can be downloaded from http://riccati.dm.unipi.it/mpsolve. It enables to deal with secular and polynomial equations where the real or complex input data can take either the approximate form of floating point numbers or the exact form of integers and rationals. The implementation exploits the parallel architecture of the computing platform.
From the many numerical experiments that we have performed our code, even though applied without the parallelism, is generally faster than MPSolve and Eigensolve. For certain polynomials it is dramatically faster. The speed up that it reaches when using multicore hardware is close to optimal. Just to make an example, for the partition polynomial of degree 72.000 which has integer coefficients representable with several megabytes, MPSolve 2.0 took about 30 days to compute all the roots [15]. Our code computes the roots in less than 2 h whereas Eigensolve has an estimated CPU time of many years.
The paper is organized as follows. In Section 2 we recall the strategies of MPSolve and Eigensolve, and give an overview of our algorithm. In Section 3 we develop the numerical tools that we need. In particular we provide a backward stable method for computing S(x), and we extend the definition and the properties of root-neighborhoods [16] and [17] from polynomials to secular functions. These properties allow us to devise effective stop conditions to halt the Ehrlich–Aberth iteration. Section 4 deals with the matrix representation of the problem and with the way of constructing different secular functions having the same roots as S(x) and using different sets of nodes. We refer to these functions as equivalent functions. Gerschgorin-like inclusion results are given and used for devising a posteriori error bounds. In Section 5 we perform a perturbation analysis of the roots of secular functions where we show that the condition number of the roots converges to zero as the nodes, used for representing the equivalent secular function, converge to the roots. The Ehrlich–Aberth iteration is recalled in Section 6. Finally, in Section 7 we present the results of the numerical experiments.
2. Overview of the algorithm
Our algorithm performs computations in floating point arithmetic with a variable number of digits. Since high precision arithmetic is expensive, our goal is to keep the number of digits of the floating point computation as low as possible. We will refer to the working precision as to the number w of binary digits used in the current floating point computation and denote u=2−w the corresponding machine precision . Recall that the standard IEEE double precision arithmetic has w=53 bits.
Here we provide an overview of our algorithm. First, we recall two different strategies to manage the working precision for computing roots of polynomials: the strategy of MPSolve and the one of Eigensolve. Then we describe the new approach which combines the two different techniques. To better explain this, we need to anticipate the following tools and concepts which will be better clarified and investigated in the next sections.
Set of inclusion disks is a set of disks in the complex plane, say provided by the Gerschgorin theorem, such that their union contains all the roots, and any connected component formed by k disks contains k roots. This way, isolated disks contain only one root.
Newton-isolated disks. A disk in a set of inclusion disks is said Newton isolated, or simply isolated , if its distance from the closest disk in the set is at least 3n times its radius. This way, if the disks include the roots of a polynomial p(x), Newton’s iteration applied to p(x) starting from the center of a Newton isolated disk converges quadratically right from the start to the root in this disk in view of [18].
Ehrlich–Aberth (EA) iteration. It is defined by the sequence of vectors such that
equation(3)
Turn MathJax on
An analogous sequence can be generated in the Gauss–Seidel style. The Newton correction N(x) can be expressed in terms of S(x) as
equation(4)
Turn MathJax on
If convergent, the sequence x(k) converges to the n-tuple of the roots of p(x); convergence to simple roots is locally cubic, it is linear for multiple roots. There is no proof of the global convergence of the EA iteration, however, from the practical point of view, no results where the sequence fails to converge have been encountered. In the practical use of this iteration, some control can be set for non-convergence. A nice feature of the iteration (3) is that it can be applied selectively only for the subscripts i of interest. The cost per iteration is O(nk) arithmetic operations (ops) where k is the number of subscripts i to which the iteration is applied. Another nice feature is that the iteration can be easily parallelized. The EA iteration performs implicit deflation of the roots without computing quotient and remainder and, unlike the iterations based on explicit deflation, it is self correcting.
Root-neighborhood. For a polynomial and a given ϵ>0, the ϵ-root-neighborhood of p(x) is the set formed by the roots of all the polynomials , where . The ϵ-root-neighborhood of is the set formed by the roots of the secular function , where .
The general lines of the strategy on which MPSolve is based are reported below. Here, the goal is to arrive at isolating all the roots up to d guaranteed correct digits.
1.
The EA iteration is applied with a working precision of w=53 bits until all the approximations are in the ϵ-root-neighborhood for ϵ=γun,u=2−w, and γ is a suitable constant whose value comes from the rounding error analysis of the Horner rule.
2.
A set of inclusion disks is computed. If all the disks are isolated, then the algorithm stops and the approximations are delivered. The algorithm stops also if the overlapping disks, if any, have radii which guarantee at least d correct digits in the approximation.
3.
If there are some overlapping or non-isolated disks (unsolved clusters), then the number of digits of the working precision is doubled, i.e., we set w≔2w, and the Ehrlich–Aberth iteration (3) is applied with the new higher precision only for the indices i corresponding to the approximations in these clusters until the computed approximations are in the ϵ-root-neighborhood, ϵ=γun. The computat
Given a positive integer n and complex numbers ai,bi,i=1,…,n such that bi≠bj for i≠j and ai≠0 for i=1,…,n, consider the rational function
equation(1)
Turn MathJax on
We associate with S(x) the secular equation S(x)=0. The numbers bi and ai, for i=1,…,n are referred to as the nodes and the coefficients of the secular function S(x), respectively.
Equations of this kind are mainly encountered in the case of real nodes bi and positive coefficients ai when the roots are real. Typical examples are modifying symmetric eigenvalue problems [1], or solving the tridiagonal symmetric eigenvalue problem by means of divide and conquer techniques [2] and [3], updating the singular values of a matrix, solving least squares problems [4], invariant subspace computation [5] and more. Over the complex field, for any set of nodes and coefficients, secular equations are encountered in the solution of the eigenvalue problem for a diagonal plus rank-one matrix [6], [7], [8] and [9] and in representing generalized companion matrix pencils in the Lagrange basis especially in the framework of “polynomial algebra by values” [10].
Secular equations are also a powerful tool for attacking the polynomial root-finding problem. This is the main fact that motivates our interest in such equations. In fact, the monic polynomial of degree n
Turn MathJax on
has roots that coincide with the roots of S(x). Moreover, one can verify that
equation(2)
Turn MathJax on
so that, given the polynomial p(x) and the nodes bi it is not expensive to compute the coefficients ai and to reformulate the polynomial root-finding problem in terms of a secular equation.
In this paper we present a method for the numerical solution of secular equations together with its computational analysis. More precisely we describe, analyze and implement an algorithm which, given in input the coefficients ai and the nodes bi,i=1,…,n of the secular function S(x) together with an integer d, provides in output the roots of S(x) represented with d guaranteed digits. In its cheaper version (isolation), the algorithm can provide approximations to the roots with the minimum number of digits sufficient to separate them from each other. The maximum number d of digits is used only for those roots, if any, which cannot be otherwise separated.
The algorithm can be effectively used as a tool for computing an arbitrarily large number d of digits of the roots of a polynomial p(x) assigned either in terms of its coefficients in some polynomial basis or by means of a black box which, given in input a complex number x, provides in output the complex number p(x). In fact we will show that using the representation of a polynomial in terms of secular equation provides substantial computational advantages.
The method relies on the combination of two different strategies to reduce the required precision of the floating point arithmetic: the strategy adopted in the package of MPSolve of D. Bini and G. Fiorentino [11], and that used in the package Eigensolve of S. Fortune [12]. It exploits some theoretical results, that we present in this paper, concerning root-neighborhoods, numerical conditioning, a posteriori error bounds, and rounding error analysis, related to computations with secular functions. It relies also on the formulation of the problem given in terms of structured matrices and on the Ehrlich–Aberth iteration as main approximation engine [13] and [14].
The algorithm that we have obtained has been implemented in the language C and incorporated in the package MPSolve originating the release MPSolve 3.0. The software is free and can be downloaded from http://riccati.dm.unipi.it/mpsolve. It enables to deal with secular and polynomial equations where the real or complex input data can take either the approximate form of floating point numbers or the exact form of integers and rationals. The implementation exploits the parallel architecture of the computing platform.
From the many numerical experiments that we have performed our code, even though applied without the parallelism, is generally faster than MPSolve and Eigensolve. For certain polynomials it is dramatically faster. The speed up that it reaches when using multicore hardware is close to optimal. Just to make an example, for the partition polynomial of degree 72.000 which has integer coefficients representable with several megabytes, MPSolve 2.0 took about 30 days to compute all the roots [15]. Our code computes the roots in less than 2 h whereas Eigensolve has an estimated CPU time of many years.
The paper is organized as follows. In Section 2 we recall the strategies of MPSolve and Eigensolve, and give an overview of our algorithm. In Section 3 we develop the numerical tools that we need. In particular we provide a backward stable method for computing S(x), and we extend the definition and the properties of root-neighborhoods [16] and [17] from polynomials to secular functions. These properties allow us to devise effective stop conditions to halt the Ehrlich–Aberth iteration. Section 4 deals with the matrix representation of the problem and with the way of constructing different secular functions having the same roots as S(x) and using different sets of nodes. We refer to these functions as equivalent functions. Gerschgorin-like inclusion results are given and used for devising a posteriori error bounds. In Section 5 we perform a perturbation analysis of the roots of secular functions where we show that the condition number of the roots converges to zero as the nodes, used for representing the equivalent secular function, converge to the roots. The Ehrlich–Aberth iteration is recalled in Section 6. Finally, in Section 7 we present the results of the numerical experiments.
2. Overview of the algorithm
Our algorithm performs computations in floating point arithmetic with a variable number of digits. Since high precision arithmetic is expensive, our goal is to keep the number of digits of the floating point computation as low as possible. We will refer to the working precision as to the number w of binary digits used in the current floating point computation and denote u=2−w the corresponding machine precision . Recall that the standard IEEE double precision arithmetic has w=53 bits.
Here we provide an overview of our algorithm. First, we recall two different strategies to manage the working precision for computing roots of polynomials: the strategy of MPSolve and the one of Eigensolve. Then we describe the new approach which combines the two different techniques. To better explain this, we need to anticipate the following tools and concepts which will be better clarified and investigated in the next sections.
Set of inclusion disks is a set of disks in the complex plane, say provided by the Gerschgorin theorem, such that their union contains all the roots, and any connected component formed by k disks contains k roots. This way, isolated disks contain only one root.
Newton-isolated disks. A disk in a set of inclusion disks is said Newton isolated, or simply isolated , if its distance from the closest disk in the set is at least 3n times its radius. This way, if the disks include the roots of a polynomial p(x), Newton’s iteration applied to p(x) starting from the center of a Newton isolated disk converges quadratically right from the start to the root in this disk in view of [18].
Ehrlich–Aberth (EA) iteration. It is defined by the sequence of vectors such that
equation(3)
Turn MathJax on
An analogous sequence can be generated in the Gauss–Seidel style. The Newton correction N(x) can be expressed in terms of S(x) as
equation(4)
Turn MathJax on
If convergent, the sequence x(k) converges to the n-tuple of the roots of p(x); convergence to simple roots is locally cubic, it is linear for multiple roots. There is no proof of the global convergence of the EA iteration, however, from the practical point of view, no results where the sequence fails to converge have been encountered. In the practical use of this iteration, some control can be set for non-convergence. A nice feature of the iteration (3) is that it can be applied selectively only for the subscripts i of interest. The cost per iteration is O(nk) arithmetic operations (ops) where k is the number of subscripts i to which the iteration is applied. Another nice feature is that the iteration can be easily parallelized. The EA iteration performs implicit deflation of the roots without computing quotient and remainder and, unlike the iterations based on explicit deflation, it is self correcting.
Root-neighborhood. For a polynomial and a given ϵ>0, the ϵ-root-neighborhood of p(x) is the set formed by the roots of all the polynomials , where . The ϵ-root-neighborhood of is the set formed by the roots of the secular function , where .
The general lines of the strategy on which MPSolve is based are reported below. Here, the goal is to arrive at isolating all the roots up to d guaranteed correct digits.
1.
The EA iteration is applied with a working precision of w=53 bits until all the approximations are in the ϵ-root-neighborhood for ϵ=γun,u=2−w, and γ is a suitable constant whose value comes from the rounding error analysis of the Horner rule.
2.
A set of inclusion disks is computed. If all the disks are isolated, then the algorithm stops and the approximations are delivered. The algorithm stops also if the overlapping disks, if any, have radii which guarantee at least d correct digits in the approximation.
3.
If there are some overlapping or non-isolated disks (unsolved clusters), then the number of digits of the working precision is doubled, i.e., we set w≔2w, and the Ehrlich–Aberth iteration (3) is applied with the new higher precision only for the indices i corresponding to the approximations in these clusters until the computed approximations are in the ϵ-root-neighborhood, ϵ=γun. The computat
0/5000
1. บทนำจำนวนเต็มบวก n และซ้อน ai, bi ฉัน = 1,..., n ดังกล่าวว่า bi≠bj i≠j และ ai≠0 หา = 1,..., n พิจารณาฟังก์ชันตรรกยะequation(1)เปิด MathJaxเราเชื่อมโยงกับ S(x) สมการทางโลก S (x) = 0 หมายเลขสองและอาย หา = 1,..., n จะเรียกว่าโหนและสัมประสิทธิ์ของฟังก์ชันทางโลก S(x) ตามลำดับสมการชนิดนี้ส่วนใหญ่จะพบในกรณีที่สองโหนจริงและบวกค่าสัมประสิทธิ์ไอเมื่อรากจริง ตัวอย่างโดยทั่วไปจะปรับเปลี่ยนปัญหา eigenvalue สมมาตร [1], หรือแก้ปัญหาโดยวิธีของ eigenvalue สมมาตร tridiagonal หาร และพิชิตเทคนิค [2] และ [3], การอัพเดตค่าเอกพจน์ของเมทริกซ์ แก้อย่างน้อยสี่เหลี่ยมปัญหา [4], คำนวณ subspace ภาษา [5] และอื่น ๆ เหนือฟิลด์ซับซ้อน การตั้งค่าใด ๆ ของโหนดและสัมประสิทธิ์ พบสมการทางโลกในการแก้ปัญหาของปัญหา eigenvalue เส้นทแยงมุม บวกอันดับหนึ่งเมทริกซ์ [6], [7], [8] และ [9] และในการแสดงดินสอเมตริกซ์สหายในโรงแรมลากรองจ์พื้นฐานโดยเฉพาะอย่างยิ่งในกรอบของ "พหุนามพีชคณิตโดยค่า" ที่ตั้งค่าทั่วไป [10]สมการทางโลกยังมีเครื่องมือที่มีประสิทธิภาพสำหรับการโจมตีปัญหาค้นหารากพหุนาม นี่คือหลักความเป็นจริงที่เราสนใจในสมการเช่นแรงบันดาลใจ ในความเป็นจริง โพลิโนเมีย monic ของ n องศาเปิด MathJaxมีรากที่ลงรอยกับรากของ S(x) นอกจากนี้ หนึ่งสามารถตรวจสอบว่าequation(2)เปิด MathJaxเพื่อว่า p(x) พหุนามและสองโหน ไม่แพงคำนวณไอสัมประสิทธิ์ และ reformulate ปัญหาค้นหารากพหุนามในรูปแบบของสมการทางโลกในเอกสารนี้ เรานำเสนอวิธีการแก้ปัญหาตัวเลขของสมการทางโลกกับการวิเคราะห์การคำนวณ ได้แม่นยำมากเราอธิบาย วิเคราะห์ และใช้อัลกอริทึมการที่ ให้เข้าไอสัมประสิทธิ์และสองโหน ฉัน = 1,..., n ของฟังก์ชันทางโลก S(x) กับ d เต็ม แสดงผลลัพธ์ของ S(x) มีรับประกันตำแหน่ง d ในรุ่นถูกกว่าของ (แยก), อัลกอริทึมสามารถให้เพียงการประมาณการรากด้วยหมายเลขต่ำสุดของตัวเลขที่เพียงพอที่จะแยกออกจากกัน D หมายเลขสูงสุดของตัวเลขจะใช้รากเหล่านี้ ถ้ามี ซึ่งไม่สามารถแยกออกได้หรืออัลกอริทึมมีประสิทธิภาพใช้เป็นเครื่องมือสำหรับการคำนวณหมายเลข d ขนาดใหญ่โดยตำแหน่งของรากของ p(x) เป็นพหุนามที่กำหนดทั้งใน ด้านของสัมประสิทธิ์ ในบางเกณฑ์พหุนาม หรือโดยการ ใช้กล่องดำป้อนข้อมูลใด กำหนดใน x เลขซับซ้อน แสดงผลลัพธ์ p(x) จำนวนเชิงซ้อน ในความเป็นจริงเราจะแสดงว่า ใช้แทนของพหุนามในรูปแบบของสมการทางโลกให้พบข้อดีคอมพิวเตอร์วิธีการอาศัยการรวมกันของสองกลยุทธ์ต่าง ๆ เพื่อลดความแม่นยำของจุดลอยตัวทางคณิตศาสตร์จำเป็น: กลยุทธ์ที่นำมาใช้ในแพคเกจของ MPSolve D. Bini G. Fiorentino [11], และที่ใช้ในแพคเกจ Eigensolve S. โชค [12] จะนำผลทฤษฎีบาง ที่เรานำเสนอในเอกสารนี้ เกี่ยวกับรากละแวกใกล้เคียง ตัวเลข ปรับขอบเขตข้อผิดพลาด posteriori และการปัดเศษข้อผิดพลาดวิเคราะห์ เกี่ยวข้องกับประมวลผลด้วยฟังก์ชันทางโลก มันใช้ยังแบ่งปัญหาที่กำหนดในโครงสร้างของเมทริกซ์ และ การเกิดซ้ำ Ehrlich – Aberth เป็นเครื่องยนต์หลักประมาณ [13] [14]อัลกอริทึมที่เราได้รับถูกนำมาใช้ในภาษา C และรวมอยู่ในแพคเกจมารุ่น MPSolve 3.0 MPSolve ซอฟต์แวร์ฟรี และสามารถดาวน์โหลดได้จาก http://riccati.dm.unipi.it/mpsolve จะช่วยให้สามารถจัดการกับทางโลก และพหุนามสมการซึ่งข้อมูลที่ป้อนเข้าจริง หรือซับซ้อนสามารถใช้แบบฟอร์มโดยประมาณจำนวนจุดลอยตัวหรือแบบจำนวนเต็มและ rationals แน่นอน ดำเนินการนำแพลตฟอร์มคอมพิวเตอร์สถาปัตยกรรมแบบขนานจากทดลองตัวเลขมากมาย ที่เราได้ทำรหัสของเรา แม้ใช้ไม่ parallelism ได้โดยทั่วไปเร็วกว่า MPSolve และ Eigensolve บาง polynomials ได้เร็วขึ้นอย่างมาก ความเร็วขึ้นถึงเมื่อใช้ฮาร์ดแวร์ multicore มีประสิทธิภาพสูงสุด เพื่อให้ตัวอย่าง สำหรับพาร์ติชันพหุนามปริญญา 72.000 ซึ่งมีสัมประสิทธิ์จำนวนเต็ม representable มีหลายเมกะไบต์ MPSolve 2.0 ใช้เวลาประมาณ 30 วันการคำนวณทั้งหมดราก [15] รหัสของเราตัวรากในน้อยกว่าในขณะที่ Eigensolve มีเวลา CPU การประเมินหลายปีกระดาษมีการจัดระเบียบดังนี้ ในส่วนที่ 2 เราเรียกคืนกลยุทธ์ของ MPSolve และ Eigensolve และให้ภาพของอัลกอริทึมของเรา ใน 3 ส่วน เราพัฒนาเครื่องมือเป็นตัวเลขที่เราต้องการ โดยเฉพาะอย่างยิ่ง เรามีวิธีมั่นคงย้อนหลังสำหรับระบบคอมพิวเตอร์ S(x) และเราขยายคำนิยามและคุณสมบัติของรากละแวกใกล้เคียง [16] [17] จาก polynomials กับฟังก์ชันทางโลก คุณสมบัติเหล่านี้ทำให้เราวางเงื่อนไขผลหยุดยั้งเกิดซ้ำ Ehrlich – Aberth ส่วน 4 ข้อเสนอแทนเมทริกซ์ของปัญหา และวิธีการสร้างแตกต่างกันทางโลกฟังก์ชันมีรากเดียวกันเป็น S(x) และใช้ค่าของโหน เราอ้างอิงถึงฟังก์ชันนี้เป็นฟังก์ชันที่เทียบเท่า ผลรวมเช่น Gerschgorin ให้ และใช้สำหรับการทบทวนขอบเขต posteriori มีข้อผิดพลาด ใน 5 ส่วนที่เราทำการ วิเคราะห์แบบ perturbation ของฟังก์ชันที่ที่เราแสดงว่า เงื่อนไขจำนวนราก converges เป็นศูนย์เป็นโหน ใช้สำหรับแทนเทียบเท่ากับฟังก์ชันทางโลก ทางโลกจึงทำให้ราก เกิดซ้ำ Ehrlich – Aberth จะยกเลิกในมาตรา ๖ สุดท้าย ในส่วน 7 เรานำเสนอผลการทดลองเป็นตัวเลข2. ภาพรวมของขั้นตอนวิธีการอัลกอริทึมของเราทำการประมวลผลในจุดทางคณิตศาสตร์กับตัวแปรจำนวนตัวเลขลอย เนื่องจากเลขคณิตความแม่นยำสูงราคาแพง เป้าหมายของเราคือเพื่อ ให้ตัวเลขของลอยจุดต่ำสุดที่สามารถคำนวณ เราจะหมายถึงความแม่นยำในการทำงานเป็น w หมายเลขใช้ในการคำนวณจุดลอยปัจจุบันตัวเลขไบนารี และแสดง u = 2−w ความแม่นยำเครื่องสอดคล้องกัน นึกว่า คู่ความแม่นยำคณิตศาสตร์มาตรฐานของ IEEE ได้ w = 53 บิตที่นี่เรามีภาพของอัลกอริทึมของเรา เรายกสองกลยุทธ์ต่าง ๆ เพื่อจัดการความแม่นยำในการทำงานสำหรับการคำนวณของ polynomials: กลยุทธ์หนึ่งของ Eigensolve และ MPSolve แล้ว เราอธิบายถึงวิธีการใหม่ที่ผสมผสานเทคนิคต่าง ๆ สอง ดีกว่า อธิบายนี้ เราจำเป็นต้องมีเครื่องมือต่อไปนี้ และแนวคิดที่จะละเอียด และตรวจสอบในส่วนถัดไปชุดดิสก์รวมเป็นชุดของดิสก์ในระนาบเชิงซ้อน พูดให้ โดยทฤษฎีบท Gerschgorin เช่นที่สหภาพของพวกเขาประกอบด้วยรากทั้งหมด และคอมโพเนนต์การเชื่อมต่อที่เกิดขึ้นจาก ดิสก์ k ประกอบด้วยราก k ด้วยวิธีนี้ แยกดิสก์ประกอบด้วยรากเดียวดิสก์แยกต่างหากนิวตัน ดิสก์ในชุดของดิสก์รวมว่า นิวตันแยกต่างหาก หรือเพียงแค่แยก ต่างหาก ถ้าจากดิสก์สุดในชุดเป็นอย่างน้อย 3 คืนเวลารัศมีของมัน ด้วยวิธีนี้ หากดิสก์มีรากของ p(x) พหุนาม ของนิวตันเกิดซ้ำกับ p(x) ที่เริ่มต้นจากศูนย์กลางของดิสก์แยกนิวตัน converges quadratically จากจุดเริ่มต้นไปยังรากในดิสก์นี้มุมมอง [18]การเกิดซ้ำ Ehrlich – Aberth (เอ) มันถูกกำหนด โดยลำดับของเวกเตอร์ที่equation(3)เปิด MathJaxคุณสามารถสร้างลำดับการคู่แบบเกาส์-Seidel สามารถแสดงการแก้ไขนิวตัน N(x) ใน S(x) เป็นequation(4)เปิด MathJaxถ้า convergent, x(k) ลำดับ converges การ n-ทูเพิลของรากของ p(x) บรรจบกันกับรากง่ายภายในลูกบาศก์ เป็นเส้นตรงสำหรับหลายราก มีไม่มีหลักฐานของการเข้าหาส่วนกลางของการเกิดซ้ำเอ อย่างไรก็ตาม จากจุดมุมมองที่เป็นประโยชน์ การพบผลไม่ที่ลำดับที่ไม่สามารถมาบรรจบกัน ในทางปฏิบัติใช้คำซ้ำนี้ สามารถตั้งควบคุมบางสำหรับไม่บรรจบกัน คุณสมบัติที่ดีของการเกิดซ้ำ (3) คือ ว่า มันสามารถใช้เลือกสำหรับตัวห้อยฉันสนใจ ต้นทุนต่อการเกิดซ้ำคือ การดำเนินงานทางคณิตศาสตร์ O(nk) (ops) โดยที่ k คือ จำนวนตัวห้อยผมใช้ที่เกิดซ้ำ คุณสมบัติที่ดีอีกคือ ว่า การเกิดซ้ำสามารถมีได้ parallelized เกิดซ้ำเอดำเนินมาตรการนัยของราก โดยคำนวณผลหารและส่วนที่เหลือ และ ไม่เหมือนซ้ำตามมาตรการชัดเจน มันเป็นการแก้ไขตนเองรากพื้นที่ใกล้เคียง พหุนามและϵกำหนด > 0 ϵ-รากใกล้กับ p(x) เป็นชุดที่เกิดขึ้นจากรากของ polynomials ทั้งหมด ที่ ชุดที่เกิดขึ้นจากรากของฟังก์ชันทางโลก เป็นϵ-รากพื้นที่ใกล้เคียงของที่มีรายงานรายการทั่วไปของกลยุทธ์ที่ MPSolve อยู่ด้านล่าง ที่นี่ เป้าหมายคือการ มาแยกรากทั้งหมดถึง d รับประกันตัวเลขถูกต้อง1ใช้คำซ้ำเอกับความแม่นยำในการใช้งาน w = 53 บิตจนกว่าจะหมดการเพียงการประมาณในϵ-รากสำหรับϵ = γun, u = 2−w และγคือ ค่าคงเหมาะสมค่ามาจากการวิเคราะห์ข้อผิดพลาดปัดกฎครึ่ง2ชุดดิสก์รวมที่คำนวณ ถ้าดิสก์ทั้งหมดแยก อัลกอริทึมการหยุด และมีการนำเสนอเพียงการประมาณการ อัลกอริทึมหยุดยังถ้าดิสก์ที่ทับซ้อนกัน ถ้ามี มีรัศมีที่รับประกันหลักน้อย d ถูกต้องในการประมาณ3ถ้ามีดิสก์บางอย่างทับซ้อนกัน หรือไม่แยกต่างหาก (ยังไม่ได้แก้ไขคลัสเตอร์), แล้ว ตัวเลขของความแม่นยำในการทำงานเป็นสอง เท่า เช่น เราตั้ง w≔2w และมีใช้คำซ้ำ Ehrlich – Aberth (3) มีความแม่นยำสูงใหม่ สำหรับดัชนีฉันที่สอดคล้องกับเพียงการประมาณในคลัสเตอร์เหล่านี้จนกระทั่งเพียงการประมาณจากการคำนวณเป็นϵ-รากพื้นที่ใกล้เคียง ϵ = γun Computat
การแปล กรุณารอสักครู่..
1. บทนำ
ป.ร. ให้ไว้จำนวนเต็มบวก n และตัวเลขที่ซับซ้อน ai, สอง, i = 1, ... , n เช่นที่สอง≠ BJ for i ≠เจ ai ≠ 0 สำหรับ i = 1, ... , n พิจารณาฟังก์ชันเหตุผลสมการ ( 1) เปิด MathJax บนเราเชื่อมโยงกับ S (x) สมฆราวาส S (x) = 0 สองตัวเลขและไอสำหรับ i = 1, ... , n จะเรียกว่าโหนดและค่าสัมประสิทธิ์ของฟังก์ชั่นฆราวาส S (x) ตามลำดับ. สมชนิดนี้ส่วนใหญ่จะพบในกรณีของสองโหนดจริงและบวก ค่าสัมประสิทธิ์ ai เมื่อรากที่เป็นจริง ตัวอย่างทั่วไปกำลังปรับเปลี่ยนปัญหา eigenvalue สมมาตร [1] หรือแก้ปัญหา eigenvalue tridiagonal สมมาตรโดยใช้วิธีการแบ่งและพิชิตเทคนิค [2] และ [3] การปรับปรุงค่าเอกพจน์ของเมทริกซ์, การแก้ปัญหาน้อยสแควร์ [4] คงที่ การคำนวณสเปซได้ [5] และอื่น ๆ กว่าข้อมูลที่ซับซ้อนสำหรับชุดของโหนดและค่าสัมประสิทธิ์ใด ๆ สมการทางโลกจะพบในการแก้ปัญหาของปัญหาค่าเฉพาะสำหรับบวกเส้นทแยงมุมอันดับหนึ่งเมทริกซ์ [6] [7] [8] [9] และในการเป็นตัวแทน ดินสอเมทริกซ์สหายทั่วไปในพื้นฐานของ Lagrange โดยเฉพาะอย่างยิ่งในกรอบของ "พีชคณิตพหุนามโดยค่า" [10]. สมโลกนอกจากนี้ยังมีเครื่องมือที่มีประสิทธิภาพสำหรับการโจมตีปัญหารากหาพหุนาม นี่คือหลักความเป็นจริงที่กระตุ้นความสนใจของเราในสมการดังกล่าว ในความเป็นจริงพหุนาม monic ปริญญา n เปิด MathJax บนมีรากที่ตรงกับรากของ S (x) นอกจากนี้เราสามารถตรวจสอบว่าสมการ (2) เปิด MathJax บนเพื่อให้ได้รับการพหุนาม P (x) และต่อมน้ำ bi จะไม่แพงในการคำนวณค่าสัมประสิทธิ์ ai และ reformulate ปัญหารากหาพหุนามในแง่ของฆราวาส สม. ในบทความนี้เราจะนำเสนอวิธีการแก้ปัญหาเชิงตัวเลขของสมการฆราวาสร่วมกับการวิเคราะห์การคำนวณของ อย่างแม่นยำมากขึ้นเราจะอธิบายวิเคราะห์และใช้อัลกอริทึมที่ได้รับในการป้อนข้อมูลค่าสัมประสิทธิ์ ai และสองโหนด, i = 1, ... , n ของฟังก์ชันฆราวาส S (x) ร่วมกับ D จำนวนเต็มให้ในการส่งออกรากของ S (x) แทนด้วยตัวเลขงรับประกัน ในรุ่นที่ถูกกว่าของ (แยก) อัลกอริทึมสามารถให้ใกล้เคียงไปที่รากที่มีจำนวนต่ำสุดของตัวเลขเพียงพอที่จะแยกพวกเขาออกจากกัน ตัวเลขงสูงสุดของตัวเลขจะถูกใช้เพื่อรากเหล่านั้นถ้าใด ๆ ที่ไม่สามารถแยกออกเป็นอย่างอื่น. ขั้นตอนวิธีสามารถนำมาใช้อย่างมีประสิทธิภาพเป็นเครื่องมือสำหรับการคำนวณงจำนวนมากโดยพลการตัวเลขของรากของ P พหุนาม (x) ที่ได้รับมอบหมายทั้งในแง่ของค่าสัมประสิทธิ์ของพหุนามในพื้นฐานบางส่วนหรือโดยวิธีการของกล่องสีดำที่ได้รับในการป้อนข้อมูลตัวเลขที่ซับซ้อน x ให้ในการส่งออก P จำนวนเชิงซ้อน (x) ในความเป็นจริงเราจะแสดงให้เห็นว่าการใช้เป็นตัวแทนของพหุนามในแง่ของสมฆราวาสมีข้อดีในการคำนวณมาก. วิธีการขึ้นอยู่กับการรวมกันของสองกลยุทธ์ที่แตกต่างกันเพื่อลดความแม่นยำที่จำเป็นของจุดลอยเลขคณิต: กลยุทธ์ที่นำมาใช้ในแพคเกจของ MPSolve ของ D. Bini กรัมและ Fiorentino [11] และที่ใช้ในแพคเกจ Eigensolve ของเอสฟอร์จูน [12] มันใช้ประโยชน์จากผลทฤษฎีบางอย่างที่เรานำเสนอในบทความนี้เกี่ยวกับรากละแวกใกล้เคียง, เครื่องตัวเลขขอบเขตข้อผิดพลาด posteriori และการวิเคราะห์ข้อผิดพลาดการปัดเศษที่เกี่ยวข้องกับการคำนวณที่มีฟังก์ชั่นฆราวาส มันอาศัยยังอยู่ในการกำหนดปัญหาที่ได้รับในแง่ของการฝึกอบรมที่มีโครงสร้างและการทวน Ehrlich-Aberth เป็นเครื่องมือหลักประมาณ [13] และ [14]. ขั้นตอนวิธีการที่เราได้รับได้รับการดำเนินการในภาษา C และ บริษัท ที่จดทะเบียนใน แพคเกจที่มีต้นกำเนิด MPSolve ปล่อย MPSolve 3.0 ซอฟแวร์ฟรีและสามารถดาวน์โหลดได้จาก http://riccati.dm.unipi.it/mpsolve ซึ่งจะช่วยให้การจัดการกับสมการทางโลกและพหุนามที่ป้อนข้อมูลจริงหรือซับซ้อนสามารถใช้ทั้งรูปแบบโดยประมาณของจำนวนจุดลอยตัวหรือรูปแบบที่แน่นอนของจำนวนเต็มและ rationals การดำเนินการใช้ประโยชน์จากสถาปัตยกรรมแบบขนานของแพลตฟอร์มคอมพิวเตอร์. จากการทดลองที่เป็นตัวเลขหลายอย่างที่เราได้ดำเนินรหัสของเราแม้นำมาใช้โดยไม่ต้องขนานโดยทั่วไปเร็วกว่า MPSolve และ Eigensolve สำหรับหลายชื่อบางอย่างมันเป็นอย่างมากได้เร็วขึ้น ความเร็วที่จะถึงเมื่อใช้ฮาร์ดแวร์แบบมัลติคอร์อยู่ใกล้กับที่ดีที่สุด เพียงเพื่อให้ตัวอย่างสำหรับพาร์ทิชันพหุนามของระดับ 72.000 ซึ่งมีสัมประสิทธิ์จำนวนเต็ม representable หลายเมกะไบต์ MPSolve 2.0 ใช้เวลาประมาณ 30 วันในการคำนวณรากทั้งหมด [15] รหัสของเราคำนวณรากน้อยกว่า 2 ชั่วโมงในขณะที่ Eigensolve มีเวลา CPU ประมาณหลายปี. กระดาษมีการจัดระเบียบดังต่อไปนี้ ในส่วนที่ 2 เราจำกลยุทธ์ของ MPSolve และ Eigensolve และให้ภาพรวมของขั้นตอนวิธีการของเรา ในส่วนที่ 3 ที่เราพัฒนาเครื่องมือที่เป็นตัวเลขที่เราต้องการ โดยเฉพาะอย่างยิ่งเรามีวิธีการที่มั่นคงสำหรับการคำนวณย้อนหลัง S (x) และเราขยายคำนิยามและคุณสมบัติของที่อยู่อาศัยราก [16] และ [17] จากหลายชื่อฟังก์ชั่นฆราวาส คุณสมบัติเหล่านี้ช่วยให้เราสามารถประดิษฐ์เงื่อนไขหยุดที่มีประสิทธิภาพที่จะหยุดการย้ำ Ehrlich-Aberth หมวดที่ 4 ข้อตกลงกับตัวแทนเมทริกซ์ของปัญหาและวิธีการในการสร้างฟังก์ชั่นที่แตกต่างกันทางโลกที่มีรากเดียวกันกับ S (x) และการใช้ชุดที่แตกต่างของโหนด เราหมายถึงฟังก์ชั่นเหล่านี้เป็นฟังก์ชั่นเทียบเท่า ผลรวม Gerschgorin เหมือนจะได้รับและใช้สำหรับการณ์ขอบเขตข้อผิดพลาด posteriori ในมาตรา 5 ที่เราดำเนินการวิเคราะห์การก่อกวนของรากของฟังก์ชั่นทางโลกที่เราแสดงให้เห็นว่าจำนวนสภาพของรากลู่ให้เป็นศูนย์เป็นโหนดที่ใช้สำหรับฟังก์ชั่นที่เป็นตัวแทนของโลกเทียบเท่าบรรจบกันไปที่ราก ย้ำ Ehrlich-Aberth ถูกเรียกคืนในมาตรา 6 สุดท้ายในมาตรา 7 เรานำเสนอผลการทดลองที่เป็นตัวเลข. 2 ภาพรวมของขั้นตอนวิธีอัลกอริทึมของเราดำเนินการในการคำนวณจุดลอยเลขคณิตที่มีจำนวนตัวแปรของตัวเลข ตั้งแต่การคำนวณความแม่นยำสูงที่มีราคาแพงเป้าหมายของเราคือการทำให้จำนวนตัวเลขของการคำนวณลอยจุดที่ต่ำที่สุดเท่าที่เป็นไปได้ เราจะอ้างถึงความแม่นยำในการทำงานเป็นจำนวนวัตต์ของตัวเลขไบนารีที่ใช้ในการคำนวณจุดลอยในปัจจุบันและแสดง u = 2-W แม่นยำเครื่องที่สอดคล้องกัน จำได้ว่ามาตรฐานการคำนวณแม่นยำ IEEE คู่มี W = 53 บิต. ที่นี่เราให้ภาพรวมของขั้นตอนวิธีการของเรา อันดับแรกเราจำสองกลยุทธ์ที่แตกต่างกันในการจัดการการทำงานที่แม่นยำสำหรับการคำนวณรากของพหุนาม: กลยุทธ์ของ MPSolve และหนึ่งใน Eigensolve จากนั้นเราจะอธิบายวิธีการใหม่ที่ผสมผสานทั้งสองเทคนิคที่แตกต่างกัน ในการอธิบายที่ดีกว่านี้เราต้องที่จะคาดการณ์เครื่องมือต่อไปนี้และแนวความคิดที่จะได้รับการชี้แจงที่ดีขึ้นและการตรวจสอบในหัวข้อถัดไป. ชุดดิสก์รวมเป็นชุดของดิสก์ในระนาบซับซ้อนพูดไว้ให้โดยทฤษฎีบท Gerschgorin เช่นที่พวกเขา ยูเนี่ยนมีรากทั้งหมดและส่วนประกอบที่เชื่อมต่อใด ๆ ที่เกิดขึ้นจากดิสก์ k มีราก k วิธีนี้ดิสก์แยกมีเพียงรากหนึ่ง. ดิสก์นิวตันแยก ดิสก์ในชุดของดิสก์รวมจะกล่าวว่านิวตันแยกหรือแยกเพียงถ้าระยะห่างจากดิสก์ที่ใกล้เคียงที่สุดในชุดอย่างน้อยครั้ง 3n รัศมี วิธีนี้ถ้าดิสก์รวมถึงรากของ P พหุนาม (x), ซ้ำของนิวตันนำไปใช้กับ P (x) เริ่มต้นจากการเป็นศูนย์กลางของดิสก์แยกนิวตัน converges quadratically ขวาตั้งแต่เริ่มต้นไปยังรากในดิสก์นี้ในมุมมองของ [ 18]. Ehrlich-Aberth (EA) ซ้ำ มันถูกกำหนดโดยลำดับของเวกเตอร์ดังกล่าวว่าสมการ (3) เปิด MathJax ในลำดับคล้ายคลึงสามารถสร้างขึ้นในรูปแบบเกาส์-Seidel แก้ไขนิวตัน N (x) สามารถแสดงออกในแง่ของ S (x) เป็นสมการ (4) เปิด MathJax บนถ้าบรรจบลำดับ x (k) ลู่ไป n-tuple ของรากของ P (x); คอนเวอร์เจนซ์ไปที่รากง่ายๆคือลูกบาศก์ท้องถิ่นมันเป็นเชิงเส้นสำหรับรากหลาย มีหลักฐานของการบรรจบกันทั่วโลกของอีเอย้ำเป็น แต่จากจุดปฏิบัติของมุมมอง, ไม่มีผลลัพธ์ที่ลำดับล้มเหลวที่จะมาบรรจบกันได้รับการพบ ในการใช้งานจริงของการทำซ้ำนี้การควบคุมบางส่วนสามารถตั้งค่าสำหรับการบรรจบกันไม่ใช่ คุณลักษณะที่ดีของการทำซ้ำ (3) ก็คือว่ามันสามารถนำมาใช้การคัดเลือกเฉพาะสำหรับห้อยฉันสนใจ ค่าใช้จ่ายต่อการทำซ้ำเป็น O (NK) ดำเนินการทางคณิตศาสตร์ (OPS) ที่ k คือจำนวนห้อยฉันที่ซ้ำถูกนำไปใช้ คุณลักษณะที่ดีก็คือว่าซ้ำสามารถ parallelized ได้อย่างง่ายดาย ย้ำ EA ดำเนินภาวะเงินฝืดโดยนัยของรากโดยไม่ต้องคำนวณความฉลาดและส่วนที่เหลือและไม่เหมือนซ้ำขึ้นอยู่กับภาวะเงินฝืดอย่างชัดเจนก็คือการแก้ไขตัวเอง. รากใกล้เคียง สำหรับพหุนามและให้ε> 0 εรากย่าน P (x) เป็นชุดที่เกิดขึ้นจากรากของพหุนามทั้งหมดที่ εรากย่านคือชุดที่เกิดขึ้นจากรากของฟังก์ชั่นฆราวาสที่. สายทั่วไปของกลยุทธ์ที่ MPSolve จะขึ้นจะมีการรายงานด้านล่าง ที่นี่มีเป้าหมายที่จะประสบความสำเร็จในการแยกรากทั้งหมดถึงวันรับประกันตัวเลขที่ถูกต้อง. 1. ย้ำ EA ถูกนำไปใช้กับการทำงานที่แม่นยำของ W = 53 บิตจนใกล้เคียงทั้งหมดที่อยู่ในεรากใกล้เคียงสำหรับε = γun, u = 2-W และγเป็นค่าคงที่ที่เหมาะสมที่มีค่ามาจากการวิเคราะห์ข้อผิดพลาดการปัดเศษของกฎฮอร์เนอ. 2. ชุดของดิสก์รวมคำนวณ ถ้าดิสก์ทั้งหมดจะแยกแล้วหยุดขั้นตอนวิธีการและใกล้เคียงมีการส่งมอบ ขั้นตอนวิธีการหยุดถ้าดิสก์ที่ทับซ้อนกัน, ถ้ามีรัศมีซึ่งรับประกันอย่างน้อยงตัวเลขที่ถูกต้องในการประมาณ. 3. ถ้ามีบางดิสก์ที่ทับซ้อนกันหรือไม่แยก (กลุ่มยังไม่แก้) แล้วจำนวนตัวเลขของการทำงาน ความแม่นยำเป็นสองเท่าคือเราตั้งw≔2wและย้ำ Ehrlich-Aberth (3) ถูกนำไปใช้ด้วยความแม่นยำที่สูงขึ้นใหม่เท่านั้นสำหรับดัชนีฉันสอดคล้องกับการประมาณในกลุ่มเหล่านี้จนประมาณคำนวณอยู่ในεราก -neighborhood, ε = γun computat
ป.ร. ให้ไว้จำนวนเต็มบวก n และตัวเลขที่ซับซ้อน ai, สอง, i = 1, ... , n เช่นที่สอง≠ BJ for i ≠เจ ai ≠ 0 สำหรับ i = 1, ... , n พิจารณาฟังก์ชันเหตุผลสมการ ( 1) เปิด MathJax บนเราเชื่อมโยงกับ S (x) สมฆราวาส S (x) = 0 สองตัวเลขและไอสำหรับ i = 1, ... , n จะเรียกว่าโหนดและค่าสัมประสิทธิ์ของฟังก์ชั่นฆราวาส S (x) ตามลำดับ. สมชนิดนี้ส่วนใหญ่จะพบในกรณีของสองโหนดจริงและบวก ค่าสัมประสิทธิ์ ai เมื่อรากที่เป็นจริง ตัวอย่างทั่วไปกำลังปรับเปลี่ยนปัญหา eigenvalue สมมาตร [1] หรือแก้ปัญหา eigenvalue tridiagonal สมมาตรโดยใช้วิธีการแบ่งและพิชิตเทคนิค [2] และ [3] การปรับปรุงค่าเอกพจน์ของเมทริกซ์, การแก้ปัญหาน้อยสแควร์ [4] คงที่ การคำนวณสเปซได้ [5] และอื่น ๆ กว่าข้อมูลที่ซับซ้อนสำหรับชุดของโหนดและค่าสัมประสิทธิ์ใด ๆ สมการทางโลกจะพบในการแก้ปัญหาของปัญหาค่าเฉพาะสำหรับบวกเส้นทแยงมุมอันดับหนึ่งเมทริกซ์ [6] [7] [8] [9] และในการเป็นตัวแทน ดินสอเมทริกซ์สหายทั่วไปในพื้นฐานของ Lagrange โดยเฉพาะอย่างยิ่งในกรอบของ "พีชคณิตพหุนามโดยค่า" [10]. สมโลกนอกจากนี้ยังมีเครื่องมือที่มีประสิทธิภาพสำหรับการโจมตีปัญหารากหาพหุนาม นี่คือหลักความเป็นจริงที่กระตุ้นความสนใจของเราในสมการดังกล่าว ในความเป็นจริงพหุนาม monic ปริญญา n เปิด MathJax บนมีรากที่ตรงกับรากของ S (x) นอกจากนี้เราสามารถตรวจสอบว่าสมการ (2) เปิด MathJax บนเพื่อให้ได้รับการพหุนาม P (x) และต่อมน้ำ bi จะไม่แพงในการคำนวณค่าสัมประสิทธิ์ ai และ reformulate ปัญหารากหาพหุนามในแง่ของฆราวาส สม. ในบทความนี้เราจะนำเสนอวิธีการแก้ปัญหาเชิงตัวเลขของสมการฆราวาสร่วมกับการวิเคราะห์การคำนวณของ อย่างแม่นยำมากขึ้นเราจะอธิบายวิเคราะห์และใช้อัลกอริทึมที่ได้รับในการป้อนข้อมูลค่าสัมประสิทธิ์ ai และสองโหนด, i = 1, ... , n ของฟังก์ชันฆราวาส S (x) ร่วมกับ D จำนวนเต็มให้ในการส่งออกรากของ S (x) แทนด้วยตัวเลขงรับประกัน ในรุ่นที่ถูกกว่าของ (แยก) อัลกอริทึมสามารถให้ใกล้เคียงไปที่รากที่มีจำนวนต่ำสุดของตัวเลขเพียงพอที่จะแยกพวกเขาออกจากกัน ตัวเลขงสูงสุดของตัวเลขจะถูกใช้เพื่อรากเหล่านั้นถ้าใด ๆ ที่ไม่สามารถแยกออกเป็นอย่างอื่น. ขั้นตอนวิธีสามารถนำมาใช้อย่างมีประสิทธิภาพเป็นเครื่องมือสำหรับการคำนวณงจำนวนมากโดยพลการตัวเลขของรากของ P พหุนาม (x) ที่ได้รับมอบหมายทั้งในแง่ของค่าสัมประสิทธิ์ของพหุนามในพื้นฐานบางส่วนหรือโดยวิธีการของกล่องสีดำที่ได้รับในการป้อนข้อมูลตัวเลขที่ซับซ้อน x ให้ในการส่งออก P จำนวนเชิงซ้อน (x) ในความเป็นจริงเราจะแสดงให้เห็นว่าการใช้เป็นตัวแทนของพหุนามในแง่ของสมฆราวาสมีข้อดีในการคำนวณมาก. วิธีการขึ้นอยู่กับการรวมกันของสองกลยุทธ์ที่แตกต่างกันเพื่อลดความแม่นยำที่จำเป็นของจุดลอยเลขคณิต: กลยุทธ์ที่นำมาใช้ในแพคเกจของ MPSolve ของ D. Bini กรัมและ Fiorentino [11] และที่ใช้ในแพคเกจ Eigensolve ของเอสฟอร์จูน [12] มันใช้ประโยชน์จากผลทฤษฎีบางอย่างที่เรานำเสนอในบทความนี้เกี่ยวกับรากละแวกใกล้เคียง, เครื่องตัวเลขขอบเขตข้อผิดพลาด posteriori และการวิเคราะห์ข้อผิดพลาดการปัดเศษที่เกี่ยวข้องกับการคำนวณที่มีฟังก์ชั่นฆราวาส มันอาศัยยังอยู่ในการกำหนดปัญหาที่ได้รับในแง่ของการฝึกอบรมที่มีโครงสร้างและการทวน Ehrlich-Aberth เป็นเครื่องมือหลักประมาณ [13] และ [14]. ขั้นตอนวิธีการที่เราได้รับได้รับการดำเนินการในภาษา C และ บริษัท ที่จดทะเบียนใน แพคเกจที่มีต้นกำเนิด MPSolve ปล่อย MPSolve 3.0 ซอฟแวร์ฟรีและสามารถดาวน์โหลดได้จาก http://riccati.dm.unipi.it/mpsolve ซึ่งจะช่วยให้การจัดการกับสมการทางโลกและพหุนามที่ป้อนข้อมูลจริงหรือซับซ้อนสามารถใช้ทั้งรูปแบบโดยประมาณของจำนวนจุดลอยตัวหรือรูปแบบที่แน่นอนของจำนวนเต็มและ rationals การดำเนินการใช้ประโยชน์จากสถาปัตยกรรมแบบขนานของแพลตฟอร์มคอมพิวเตอร์. จากการทดลองที่เป็นตัวเลขหลายอย่างที่เราได้ดำเนินรหัสของเราแม้นำมาใช้โดยไม่ต้องขนานโดยทั่วไปเร็วกว่า MPSolve และ Eigensolve สำหรับหลายชื่อบางอย่างมันเป็นอย่างมากได้เร็วขึ้น ความเร็วที่จะถึงเมื่อใช้ฮาร์ดแวร์แบบมัลติคอร์อยู่ใกล้กับที่ดีที่สุด เพียงเพื่อให้ตัวอย่างสำหรับพาร์ทิชันพหุนามของระดับ 72.000 ซึ่งมีสัมประสิทธิ์จำนวนเต็ม representable หลายเมกะไบต์ MPSolve 2.0 ใช้เวลาประมาณ 30 วันในการคำนวณรากทั้งหมด [15] รหัสของเราคำนวณรากน้อยกว่า 2 ชั่วโมงในขณะที่ Eigensolve มีเวลา CPU ประมาณหลายปี. กระดาษมีการจัดระเบียบดังต่อไปนี้ ในส่วนที่ 2 เราจำกลยุทธ์ของ MPSolve และ Eigensolve และให้ภาพรวมของขั้นตอนวิธีการของเรา ในส่วนที่ 3 ที่เราพัฒนาเครื่องมือที่เป็นตัวเลขที่เราต้องการ โดยเฉพาะอย่างยิ่งเรามีวิธีการที่มั่นคงสำหรับการคำนวณย้อนหลัง S (x) และเราขยายคำนิยามและคุณสมบัติของที่อยู่อาศัยราก [16] และ [17] จากหลายชื่อฟังก์ชั่นฆราวาส คุณสมบัติเหล่านี้ช่วยให้เราสามารถประดิษฐ์เงื่อนไขหยุดที่มีประสิทธิภาพที่จะหยุดการย้ำ Ehrlich-Aberth หมวดที่ 4 ข้อตกลงกับตัวแทนเมทริกซ์ของปัญหาและวิธีการในการสร้างฟังก์ชั่นที่แตกต่างกันทางโลกที่มีรากเดียวกันกับ S (x) และการใช้ชุดที่แตกต่างของโหนด เราหมายถึงฟังก์ชั่นเหล่านี้เป็นฟังก์ชั่นเทียบเท่า ผลรวม Gerschgorin เหมือนจะได้รับและใช้สำหรับการณ์ขอบเขตข้อผิดพลาด posteriori ในมาตรา 5 ที่เราดำเนินการวิเคราะห์การก่อกวนของรากของฟังก์ชั่นทางโลกที่เราแสดงให้เห็นว่าจำนวนสภาพของรากลู่ให้เป็นศูนย์เป็นโหนดที่ใช้สำหรับฟังก์ชั่นที่เป็นตัวแทนของโลกเทียบเท่าบรรจบกันไปที่ราก ย้ำ Ehrlich-Aberth ถูกเรียกคืนในมาตรา 6 สุดท้ายในมาตรา 7 เรานำเสนอผลการทดลองที่เป็นตัวเลข. 2 ภาพรวมของขั้นตอนวิธีอัลกอริทึมของเราดำเนินการในการคำนวณจุดลอยเลขคณิตที่มีจำนวนตัวแปรของตัวเลข ตั้งแต่การคำนวณความแม่นยำสูงที่มีราคาแพงเป้าหมายของเราคือการทำให้จำนวนตัวเลขของการคำนวณลอยจุดที่ต่ำที่สุดเท่าที่เป็นไปได้ เราจะอ้างถึงความแม่นยำในการทำงานเป็นจำนวนวัตต์ของตัวเลขไบนารีที่ใช้ในการคำนวณจุดลอยในปัจจุบันและแสดง u = 2-W แม่นยำเครื่องที่สอดคล้องกัน จำได้ว่ามาตรฐานการคำนวณแม่นยำ IEEE คู่มี W = 53 บิต. ที่นี่เราให้ภาพรวมของขั้นตอนวิธีการของเรา อันดับแรกเราจำสองกลยุทธ์ที่แตกต่างกันในการจัดการการทำงานที่แม่นยำสำหรับการคำนวณรากของพหุนาม: กลยุทธ์ของ MPSolve และหนึ่งใน Eigensolve จากนั้นเราจะอธิบายวิธีการใหม่ที่ผสมผสานทั้งสองเทคนิคที่แตกต่างกัน ในการอธิบายที่ดีกว่านี้เราต้องที่จะคาดการณ์เครื่องมือต่อไปนี้และแนวความคิดที่จะได้รับการชี้แจงที่ดีขึ้นและการตรวจสอบในหัวข้อถัดไป. ชุดดิสก์รวมเป็นชุดของดิสก์ในระนาบซับซ้อนพูดไว้ให้โดยทฤษฎีบท Gerschgorin เช่นที่พวกเขา ยูเนี่ยนมีรากทั้งหมดและส่วนประกอบที่เชื่อมต่อใด ๆ ที่เกิดขึ้นจากดิสก์ k มีราก k วิธีนี้ดิสก์แยกมีเพียงรากหนึ่ง. ดิสก์นิวตันแยก ดิสก์ในชุดของดิสก์รวมจะกล่าวว่านิวตันแยกหรือแยกเพียงถ้าระยะห่างจากดิสก์ที่ใกล้เคียงที่สุดในชุดอย่างน้อยครั้ง 3n รัศมี วิธีนี้ถ้าดิสก์รวมถึงรากของ P พหุนาม (x), ซ้ำของนิวตันนำไปใช้กับ P (x) เริ่มต้นจากการเป็นศูนย์กลางของดิสก์แยกนิวตัน converges quadratically ขวาตั้งแต่เริ่มต้นไปยังรากในดิสก์นี้ในมุมมองของ [ 18]. Ehrlich-Aberth (EA) ซ้ำ มันถูกกำหนดโดยลำดับของเวกเตอร์ดังกล่าวว่าสมการ (3) เปิด MathJax ในลำดับคล้ายคลึงสามารถสร้างขึ้นในรูปแบบเกาส์-Seidel แก้ไขนิวตัน N (x) สามารถแสดงออกในแง่ของ S (x) เป็นสมการ (4) เปิด MathJax บนถ้าบรรจบลำดับ x (k) ลู่ไป n-tuple ของรากของ P (x); คอนเวอร์เจนซ์ไปที่รากง่ายๆคือลูกบาศก์ท้องถิ่นมันเป็นเชิงเส้นสำหรับรากหลาย มีหลักฐานของการบรรจบกันทั่วโลกของอีเอย้ำเป็น แต่จากจุดปฏิบัติของมุมมอง, ไม่มีผลลัพธ์ที่ลำดับล้มเหลวที่จะมาบรรจบกันได้รับการพบ ในการใช้งานจริงของการทำซ้ำนี้การควบคุมบางส่วนสามารถตั้งค่าสำหรับการบรรจบกันไม่ใช่ คุณลักษณะที่ดีของการทำซ้ำ (3) ก็คือว่ามันสามารถนำมาใช้การคัดเลือกเฉพาะสำหรับห้อยฉันสนใจ ค่าใช้จ่ายต่อการทำซ้ำเป็น O (NK) ดำเนินการทางคณิตศาสตร์ (OPS) ที่ k คือจำนวนห้อยฉันที่ซ้ำถูกนำไปใช้ คุณลักษณะที่ดีก็คือว่าซ้ำสามารถ parallelized ได้อย่างง่ายดาย ย้ำ EA ดำเนินภาวะเงินฝืดโดยนัยของรากโดยไม่ต้องคำนวณความฉลาดและส่วนที่เหลือและไม่เหมือนซ้ำขึ้นอยู่กับภาวะเงินฝืดอย่างชัดเจนก็คือการแก้ไขตัวเอง. รากใกล้เคียง สำหรับพหุนามและให้ε> 0 εรากย่าน P (x) เป็นชุดที่เกิดขึ้นจากรากของพหุนามทั้งหมดที่ εรากย่านคือชุดที่เกิดขึ้นจากรากของฟังก์ชั่นฆราวาสที่. สายทั่วไปของกลยุทธ์ที่ MPSolve จะขึ้นจะมีการรายงานด้านล่าง ที่นี่มีเป้าหมายที่จะประสบความสำเร็จในการแยกรากทั้งหมดถึงวันรับประกันตัวเลขที่ถูกต้อง. 1. ย้ำ EA ถูกนำไปใช้กับการทำงานที่แม่นยำของ W = 53 บิตจนใกล้เคียงทั้งหมดที่อยู่ในεรากใกล้เคียงสำหรับε = γun, u = 2-W และγเป็นค่าคงที่ที่เหมาะสมที่มีค่ามาจากการวิเคราะห์ข้อผิดพลาดการปัดเศษของกฎฮอร์เนอ. 2. ชุดของดิสก์รวมคำนวณ ถ้าดิสก์ทั้งหมดจะแยกแล้วหยุดขั้นตอนวิธีการและใกล้เคียงมีการส่งมอบ ขั้นตอนวิธีการหยุดถ้าดิสก์ที่ทับซ้อนกัน, ถ้ามีรัศมีซึ่งรับประกันอย่างน้อยงตัวเลขที่ถูกต้องในการประมาณ. 3. ถ้ามีบางดิสก์ที่ทับซ้อนกันหรือไม่แยก (กลุ่มยังไม่แก้) แล้วจำนวนตัวเลขของการทำงาน ความแม่นยำเป็นสองเท่าคือเราตั้งw≔2wและย้ำ Ehrlich-Aberth (3) ถูกนำไปใช้ด้วยความแม่นยำที่สูงขึ้นใหม่เท่านั้นสำหรับดัชนีฉันสอดคล้องกับการประมาณในกลุ่มเหล่านี้จนประมาณคำนวณอยู่ในεราก -neighborhood, ε = γun computat
การแปล กรุณารอสักครู่..
1 . บทนำ
ให้จำนวนเต็มบวก N และจำนวนเชิงซ้อน AI , บี , i = 1 , . . . , n เช่น บี≠ BJ สำหรับผม≠ J และไอ≠ 0 i = 1 , . . . , n , พิจารณาเหตุผลฟังก์ชั่นสมการ ( 1 )
เปิด mathjax บน
เราเชื่อมโยงกับเ ( x ) สมการทางโลก S ( x ) = 0 ตัวเลขบีไอ สำหรับฉัน = 1 , . . . , n จะเรียกว่าโหนด และสัมประสิทธิ์ของฟังก์ชันทางโลก S ( x )
)สมการประเภทนี้ส่วนใหญ่จะพบในกรณีของโหนดจริงบีและบวกค่าไอ เมื่อรากมีจริง ตัวอย่างทั่วไปคือการปรับเปลี่ยนค่าปัญหาสมมาตร [ 1 ] หรือการแก้ไขปัญหาค่า tridiagonal สมมาตรโดยใช้วิธีการแบ่งและพิชิตเทคนิค [ 2 ] และ [ 3 ] , การปรับปรุงค่าเอกพจน์ของเมทริกซ์ การแก้ปัญหากำลังสองน้อยสุด [ 4 ]การคำนวณค่าคงที่ได้ [ 5 ] และเพิ่มเติม ไปสนามที่ซับซ้อนสำหรับการใด ๆชุดของโหนดและค่าสัมประสิทธิ์สมการทางโลกจะพบทางออกของปัญหาค่าเส้นทแยงมุมบวกอันดับหนึ่งเมทริกซ์ [ 6 ] [ 7 ] [ 8 ] และ [ 9 ] และในตัวสหายแทนเมทริกซ์ดินสอใน Lagrange พื้นฐานโดยเฉพาะในกรอบของพหุนามพีชคณิตด้วยค่า
" [ 10 ]สมการทางโลกก็เป็นเครื่องมือที่มีประสิทธิภาพสำหรับการค้นหาพหุนามรากปัญหา นี่คือหลักความเป็นจริงที่กระตุ้นความสนใจของเราในสมการดังกล่าว ในความเป็นจริง โมนิกพหุนามองศา N
เปิด mathjax ต่อ
มีรากที่บรรจบกับรากของ S ( x ) นอกจากนี้หนึ่งสามารถตรวจสอบว่าสมการ ( 2 )
เปิด mathjax บน
ดังนั้นได้รับพหุนาม p ( x ) และโหนด บิ มันไม่แพง คำนวณหาค่าสัมประสิทธิ์ AI และ reformulate โดยรากพบปัญหาในแง่ของสมการทางโลก .
ในกระดาษนี้เรานำเสนอวิธีการหาผลเฉลยเชิงตัวเลขของสมการทางโลกร่วมกับการวิเคราะห์เชิงคำนวณของ ยิ่งกว่านั้นเราอธิบาย วิเคราะห์ และใช้อัลกอริทึมที่ให้ใส่ค่าใน AI และโหนดบี , i = 1 , . . . , n การทำงานของฆราวาส S ( x ) ร่วมกับจำนวนเต็ม D ให้ในผลผลิตรากของ S ( x ) D รับประกันแทนด้วยตัวเลข ในรุ่นของถูกกว่า ( แยก ) , ขั้นตอนวิธีการสามารถให้ใกล้เคียงกับรากกับจำนวนขั้นต่ำของตัวเลขที่เพียงพอที่จะแยกพวกเขาจากแต่ละอื่น ๆจำนวนสูงสุด D ของตัวเลขใช้เฉพาะรากเหล่านั้น ถ้าใด ๆที่ไม่สามารถเป็นอย่างอื่นแยก
อัลกอริทึมที่สามารถใช้งานได้อย่างมีประสิทธิภาพเป็นเครื่องมือสำหรับการคำนวณการโดยพลการจํานวน D ของตัวเลขของรากของพหุนาม p ( x ) ที่กำหนดให้ในแง่ของสัมประสิทธิ์พหุนามในพื้นฐานบางหรือ โดยความหมายของกล่องสีดำที่ให้ใส่เลขเชิงซ้อน Xแสดงในการแสดงผลเลขเชิงซ้อน P ( x ) ในความเป็นจริงเราจะแสดงที่ใช้เป็นตัวแทนของสมการพหุนามในแง่ของฆราวาสมีข้อได้เปรียบเชิงรูปธรรม
วิธีอาศัยการรวมกันของทั้งสองกลยุทธ์ที่แตกต่างกันจะใช้ลดความแม่นยำของจุดลอย ) : กลยุทธ์ที่ใช้ในการแพคเกจของ mpsolve D . บีนี Gฟิโอเรนติโน [ 11 ] และที่ใช้ในแพคเกจ eigensolve S . โชคลาภ [ 12 ] มันใช้ประโยชน์ผลทฤษฎีบางอย่าง ที่เรานำเสนอในบทความนี้เกี่ยวกับรากย่านปรับอากาศเชิงตัวเลข จากผลไปสู่เหตุข้อผิดพลาดการปัดเศษ ขอบเขต และการวิเคราะห์ข้อผิดพลาดที่เกี่ยวข้องกับการคำนวณด้วยฟังก์ชันใดๆมันต้องอาศัย นอกจากนี้ในการกำหนดปัญหาที่ได้รับในแง่ของโครงสร้างเมทริกซ์และทำซ้ำแน่นอน– aberth เป็นเครื่องมือประมาณหลัก [ 13 ] และ [ 14 ] .
วิธีที่เราได้รับมาประยุกต์ใช้ในภาษา C และรวมอยู่ในแพคเกจ mpsolve ที่มาปล่อย mpsolve 3.0 ซอฟต์แวร์ฟรีและสามารถดาวน์โหลดได้จาก http://riccati.dm.unipi .มัน mpsolve . มันสามารถจัดการกับฆราวาสและพหุนามสมการที่ซับซ้อนจริง หรือข้อมูลสามารถใช้รูปแบบของตัวเลขโดยประมาณจุดลอยหรือรูปแบบที่แน่นอนของจำนวนเต็มและ rationals . การใช้ประโยชน์จากสถาปัตยกรรมแบบขนานของแพลตฟอร์มคอมพิวเตอร์
จากหลายการทดลองเชิงตัวเลขที่เราแสดงรหัสของเราทั้งๆที่ใช้ไม่มีความขนาน , โดยทั่วไปจะเร็วกว่าและ mpsolve eigensolve . บางชื่อที่ประกอบด้วยหลายคำจะมากได้เร็วขึ้น ความเร็วขึ้นถึงเมื่อใช้ multicore ฮาร์ดแวร์อยู่ใกล้ที่สุด เพื่อให้ตัวอย่างสำหรับพาร์ทิชันจำนวนเต็ม 72.000 พหุนามองศาซึ่งมีสัมประสิทธิ์ representable หลายเมกะไบต์ mpsolve 20 ใช้เวลาประมาณ 30 วัน คำนวณทุกราก [ 15 ] รหัสของเราคำนวณรากในน้อยกว่า 2 ชั่วโมง ในขณะที่ eigensolve ที่มีประมาณ CPU เวลาหลายปี
กระดาษจัดดังนี้ ในส่วนที่ 2 เราเรียกกลยุทธ์ mpsolve และ eigensolve และให้ภาพรวมของวิธีการของเรา ในส่วนที่ 3 เราพัฒนาเครื่องมือที่ตัวเลขที่เราต้องการโดยเฉพาะเราให้ถอยหลังมั่นคงวิธีการคอมพิวเตอร์ S ( x ) และเราขยายนิยามและคุณสมบัติของรากย่าน [ 16 ] และ [ 17 ] จากพหุนามฟังก์ชันใดๆ คุณสมบัติเหล่านี้ช่วยให้เราสามารถสร้างเงื่อนไขหยุดที่มีประสิทธิภาพที่จะหยุดลิช – aberth ซ้ำ .ส่วนที่ 4 เกี่ยวกับเมทริกซ์เป็นตัวแทนของปัญหาด้วยวิธีของการสร้างฟังก์ชันทางโลกที่แตกต่างกันมีรากเดียวกับ S ( x ) และใช้ชุดที่แตกต่างกันของโหนด เราเรียกฟังก์ชันนี้เป็นฟังก์ชันที่เทียบเท่า ผลการ gerschgorin เหมือนจะได้รับและใช้สำหรับคิดจากผลไปสู่เหตุผิดพลาดเลยนะ
ให้จำนวนเต็มบวก N และจำนวนเชิงซ้อน AI , บี , i = 1 , . . . , n เช่น บี≠ BJ สำหรับผม≠ J และไอ≠ 0 i = 1 , . . . , n , พิจารณาเหตุผลฟังก์ชั่นสมการ ( 1 )
เปิด mathjax บน
เราเชื่อมโยงกับเ ( x ) สมการทางโลก S ( x ) = 0 ตัวเลขบีไอ สำหรับฉัน = 1 , . . . , n จะเรียกว่าโหนด และสัมประสิทธิ์ของฟังก์ชันทางโลก S ( x )
)สมการประเภทนี้ส่วนใหญ่จะพบในกรณีของโหนดจริงบีและบวกค่าไอ เมื่อรากมีจริง ตัวอย่างทั่วไปคือการปรับเปลี่ยนค่าปัญหาสมมาตร [ 1 ] หรือการแก้ไขปัญหาค่า tridiagonal สมมาตรโดยใช้วิธีการแบ่งและพิชิตเทคนิค [ 2 ] และ [ 3 ] , การปรับปรุงค่าเอกพจน์ของเมทริกซ์ การแก้ปัญหากำลังสองน้อยสุด [ 4 ]การคำนวณค่าคงที่ได้ [ 5 ] และเพิ่มเติม ไปสนามที่ซับซ้อนสำหรับการใด ๆชุดของโหนดและค่าสัมประสิทธิ์สมการทางโลกจะพบทางออกของปัญหาค่าเส้นทแยงมุมบวกอันดับหนึ่งเมทริกซ์ [ 6 ] [ 7 ] [ 8 ] และ [ 9 ] และในตัวสหายแทนเมทริกซ์ดินสอใน Lagrange พื้นฐานโดยเฉพาะในกรอบของพหุนามพีชคณิตด้วยค่า
" [ 10 ]สมการทางโลกก็เป็นเครื่องมือที่มีประสิทธิภาพสำหรับการค้นหาพหุนามรากปัญหา นี่คือหลักความเป็นจริงที่กระตุ้นความสนใจของเราในสมการดังกล่าว ในความเป็นจริง โมนิกพหุนามองศา N
เปิด mathjax ต่อ
มีรากที่บรรจบกับรากของ S ( x ) นอกจากนี้หนึ่งสามารถตรวจสอบว่าสมการ ( 2 )
เปิด mathjax บน
ดังนั้นได้รับพหุนาม p ( x ) และโหนด บิ มันไม่แพง คำนวณหาค่าสัมประสิทธิ์ AI และ reformulate โดยรากพบปัญหาในแง่ของสมการทางโลก .
ในกระดาษนี้เรานำเสนอวิธีการหาผลเฉลยเชิงตัวเลขของสมการทางโลกร่วมกับการวิเคราะห์เชิงคำนวณของ ยิ่งกว่านั้นเราอธิบาย วิเคราะห์ และใช้อัลกอริทึมที่ให้ใส่ค่าใน AI และโหนดบี , i = 1 , . . . , n การทำงานของฆราวาส S ( x ) ร่วมกับจำนวนเต็ม D ให้ในผลผลิตรากของ S ( x ) D รับประกันแทนด้วยตัวเลข ในรุ่นของถูกกว่า ( แยก ) , ขั้นตอนวิธีการสามารถให้ใกล้เคียงกับรากกับจำนวนขั้นต่ำของตัวเลขที่เพียงพอที่จะแยกพวกเขาจากแต่ละอื่น ๆจำนวนสูงสุด D ของตัวเลขใช้เฉพาะรากเหล่านั้น ถ้าใด ๆที่ไม่สามารถเป็นอย่างอื่นแยก
อัลกอริทึมที่สามารถใช้งานได้อย่างมีประสิทธิภาพเป็นเครื่องมือสำหรับการคำนวณการโดยพลการจํานวน D ของตัวเลขของรากของพหุนาม p ( x ) ที่กำหนดให้ในแง่ของสัมประสิทธิ์พหุนามในพื้นฐานบางหรือ โดยความหมายของกล่องสีดำที่ให้ใส่เลขเชิงซ้อน Xแสดงในการแสดงผลเลขเชิงซ้อน P ( x ) ในความเป็นจริงเราจะแสดงที่ใช้เป็นตัวแทนของสมการพหุนามในแง่ของฆราวาสมีข้อได้เปรียบเชิงรูปธรรม
วิธีอาศัยการรวมกันของทั้งสองกลยุทธ์ที่แตกต่างกันจะใช้ลดความแม่นยำของจุดลอย ) : กลยุทธ์ที่ใช้ในการแพคเกจของ mpsolve D . บีนี Gฟิโอเรนติโน [ 11 ] และที่ใช้ในแพคเกจ eigensolve S . โชคลาภ [ 12 ] มันใช้ประโยชน์ผลทฤษฎีบางอย่าง ที่เรานำเสนอในบทความนี้เกี่ยวกับรากย่านปรับอากาศเชิงตัวเลข จากผลไปสู่เหตุข้อผิดพลาดการปัดเศษ ขอบเขต และการวิเคราะห์ข้อผิดพลาดที่เกี่ยวข้องกับการคำนวณด้วยฟังก์ชันใดๆมันต้องอาศัย นอกจากนี้ในการกำหนดปัญหาที่ได้รับในแง่ของโครงสร้างเมทริกซ์และทำซ้ำแน่นอน– aberth เป็นเครื่องมือประมาณหลัก [ 13 ] และ [ 14 ] .
วิธีที่เราได้รับมาประยุกต์ใช้ในภาษา C และรวมอยู่ในแพคเกจ mpsolve ที่มาปล่อย mpsolve 3.0 ซอฟต์แวร์ฟรีและสามารถดาวน์โหลดได้จาก http://riccati.dm.unipi .มัน mpsolve . มันสามารถจัดการกับฆราวาสและพหุนามสมการที่ซับซ้อนจริง หรือข้อมูลสามารถใช้รูปแบบของตัวเลขโดยประมาณจุดลอยหรือรูปแบบที่แน่นอนของจำนวนเต็มและ rationals . การใช้ประโยชน์จากสถาปัตยกรรมแบบขนานของแพลตฟอร์มคอมพิวเตอร์
จากหลายการทดลองเชิงตัวเลขที่เราแสดงรหัสของเราทั้งๆที่ใช้ไม่มีความขนาน , โดยทั่วไปจะเร็วกว่าและ mpsolve eigensolve . บางชื่อที่ประกอบด้วยหลายคำจะมากได้เร็วขึ้น ความเร็วขึ้นถึงเมื่อใช้ multicore ฮาร์ดแวร์อยู่ใกล้ที่สุด เพื่อให้ตัวอย่างสำหรับพาร์ทิชันจำนวนเต็ม 72.000 พหุนามองศาซึ่งมีสัมประสิทธิ์ representable หลายเมกะไบต์ mpsolve 20 ใช้เวลาประมาณ 30 วัน คำนวณทุกราก [ 15 ] รหัสของเราคำนวณรากในน้อยกว่า 2 ชั่วโมง ในขณะที่ eigensolve ที่มีประมาณ CPU เวลาหลายปี
กระดาษจัดดังนี้ ในส่วนที่ 2 เราเรียกกลยุทธ์ mpsolve และ eigensolve และให้ภาพรวมของวิธีการของเรา ในส่วนที่ 3 เราพัฒนาเครื่องมือที่ตัวเลขที่เราต้องการโดยเฉพาะเราให้ถอยหลังมั่นคงวิธีการคอมพิวเตอร์ S ( x ) และเราขยายนิยามและคุณสมบัติของรากย่าน [ 16 ] และ [ 17 ] จากพหุนามฟังก์ชันใดๆ คุณสมบัติเหล่านี้ช่วยให้เราสามารถสร้างเงื่อนไขหยุดที่มีประสิทธิภาพที่จะหยุดลิช – aberth ซ้ำ .ส่วนที่ 4 เกี่ยวกับเมทริกซ์เป็นตัวแทนของปัญหาด้วยวิธีของการสร้างฟังก์ชันทางโลกที่แตกต่างกันมีรากเดียวกับ S ( x ) และใช้ชุดที่แตกต่างกันของโหนด เราเรียกฟังก์ชันนี้เป็นฟังก์ชันที่เทียบเท่า ผลการ gerschgorin เหมือนจะได้รับและใช้สำหรับคิดจากผลไปสู่เหตุผิดพลาดเลยนะ
การแปล กรุณารอสักครู่..
ภาษาอื่น ๆ
การสนับสนุนเครื่องมือแปลภาษา: กรีก, กันนาดา, กาลิเชียน, คลิงออน, คอร์สิกา, คาซัค, คาตาลัน, คินยารวันดา, คีร์กิซ, คุชราต, จอร์เจีย, จีน, จีนดั้งเดิม, ชวา, ชิเชวา, ซามัว, ซีบัวโน, ซุนดา, ซูลู, ญี่ปุ่น, ดัตช์, ตรวจหาภาษา, ตุรกี, ทมิฬ, ทาจิก, ทาทาร์, นอร์เวย์, บอสเนีย, บัลแกเรีย, บาสก์, ปัญจาป, ฝรั่งเศส, พาชตู, ฟริเชียน, ฟินแลนด์, ฟิลิปปินส์, ภาษาอินโดนีเซี, มองโกเลีย, มัลทีส, มาซีโดเนีย, มาราฐี, มาลากาซี, มาลายาลัม, มาเลย์, ม้ง, ยิดดิช, ยูเครน, รัสเซีย, ละติน, ลักเซมเบิร์ก, ลัตเวีย, ลาว, ลิทัวเนีย, สวาฮิลี, สวีเดน, สิงหล, สินธี, สเปน, สโลวัก, สโลวีเนีย, อังกฤษ, อัมฮาริก, อาร์เซอร์ไบจัน, อาร์เมเนีย, อาหรับ, อิกโบ, อิตาลี, อุยกูร์, อุสเบกิสถาน, อูรดู, ฮังการี, ฮัวซา, ฮาวาย, ฮินดี, ฮีบรู, เกลิกสกอต, เกาหลี, เขมร, เคิร์ด, เช็ก, เซอร์เบียน, เซโซโท, เดนมาร์ก, เตลูกู, เติร์กเมน, เนปาล, เบงกอล, เบลารุส, เปอร์เซีย, เมารี, เมียนมา (พม่า), เยอรมัน, เวลส์, เวียดนาม, เอสเปอแรนโต, เอสโทเนีย, เฮติครีโอล, แอฟริกา, แอลเบเนีย, โคซา, โครเอเชีย, โชนา, โซมาลี, โปรตุเกส, โปแลนด์, โยรูบา, โรมาเนีย, โอเดีย (โอริยา), ไทย, ไอซ์แลนด์, ไอร์แลนด์, การแปลภาษา.
- ไดโนเสาร์เป็นสัตว์ดึกดำบรรพ์ซึ่งมีชีวิตอ
- เนื่องด้วยปัจจัยทางภูมิศาสตร์ สภาพภูมิอา
- 1.Workgroup-inspired work procedures
- ขายอะไหล่
- เขาเอาหัวโขกกำแพง
- ใช้ชีวิตให้คุ้มค่า
- Kindly provide the pressure test report
- เนื่องด้วยปัจจัยทางภูมิศาสตร์ สภาพภูมิอา
- Muck baby :)
- เขาทำงานเป็นเจ้าหน้าที่ฝ่ายบุคคลอยู่ที่โ
- small
- Table 3 summarizes the concentrations of
- ประตูสวิง Painting Workshop
- เครื่องโปรเจคเตอร์ SANYO
- In this research, the views of the stude
- ฉู่ปลาแซวม่อน
- This last stage is necessary only to det
- 2. Collective responsibility facilitates
- ตอนเย็น
- i mean how many men interest in you deal
- ฉันพูดคุยกับผู้ก่อการร้าย
- And i only want what is best for u.
- แม่ค้าพูดเพราะ
- She has been employing by LMG
